Have you tried deleting from Explorer? Do you have multiple media players that save song lists?

I had a similar problem with both Music Match Jukebox and Windows Media Player, I've found that if I don't save the song lists in the library, I don't get that message. This glitch will also keep you from renaming files that have either the wrong title or the wrong artist, which you can't do if the file is "in use" by another program whether that program is open or not.

Or it could be something else entirely.