You need to remember that library's only point to the actual file somewhere on the network or on your own machine in the "user" files. If you need to delate something from the library you should delate the file from the actual source "my pictures" My documents" "my music".
But there is a way to make it work like you want.
Just go into Windows Media Player, choose the "organize" tab then "options" then choose the Library tab and set it to "delate files from the computer when delated from the Library. Although I believe that only works if you are delating files from Library of the machine that contains the source files.
That should allow for delating from the Library, but only from the machine that the files reside on, I don't believe it will work accross the network. It think it still works best if you delate from the file source instead of the Library.