One possible reason... is your iTunes library stored on an external drive? (ie. the song files themselves, NOT the iTunes library files that is in your ~/Music folder)
A user can set the default location for all of the MEDIA files onto an external drive and as long as the default library has its location set to this location all should work just as it would if the media files were stored in the user's home directory location. (i.e. ~/Music/iTunes)
IF this drive is either having problems with permissions (more than the likely culprit here) or the drive is not mounted, iTunes will by default use the normal path to the user's home directory and NOT the path specified by the user. Music (or other media) deleted from the main library will NOT get moved to the trash should this be the case. The entry in the XML database for the track is the ONLY thing deleted as it has no reference within it to point to the actual file to delete it.
I use an external 1TB drive to house all of my media files used by iTunes and it works for me as I've got over 60K of tracks in my system and there just isn't enough space on the internal drive of my MacBook to store them.