I am using a Droid X with rooted Gingerbread that is otherwise stock. I have root access, but have not used it to do anything.
I have inspected the /Music folder multiple times and the 500+ songs I deleted are physically not in the filesystem any more. I tried rebooting the phone multiple times. I tried deleting the Cache and data for the app in Settings > Application, as well as running SDrescan to remount and rescan the card. I even tried deleting them from the music player app itself.
No matter what I try, these songs will not disappear. (Though they obviously fail when I try to play them because they don't exist) Is there a file where the Music library cache is being kept that isn't getting updated? I would love to find it and just delete it.
I also use Songbird for Android, and it had the same problem. New songs show up, but the old ones will not go away at all. Though, now Songbird won't even load at all. Sometimes loading it causes the phone to reboot. I have currently uninstalled it.
In addition, it causes the phone to become very unstable whenever I try to play music. Accidentally playing a non-existent song can cause the phone to crash and get stuck on a black screen, requiring a battery pull and reboot.