Well, there are people here who know this stuff better than I do, but I once had a virus which did this. Turns out that it had changed some mp3s into hidden files. One way to check for this is just to go to tools->folder options->view and click on "show hidden files and folders." If it turns out that your files are hidden, you can change them back by right-clicking on them and de-selecting the hidden attribute. I hope it's not a virus (if it is, it's almost definitely not the same one I had; that was years ago), but a full virus-scan probably wouldn't hurt in any event. Good luck.
They are just GONE! And now I'm getting a popup whenever I play a mp3. About 20 seconds into any song, a popup comes on from the 'RIAA' directing me to a bogus russian website wanting me to buy music from it.
I don't know how current that is, but checking google for "riaa virus mp3" found a few sites mentioning this. No solutions in the first few clicks though.
My best advice would be to stop using the drives that have had mp3s deleted from and try using a dos based 'undelete' program. When files are deleted, they aren't actually "gone" until the space on the hard drive has been used again. They are hidden from your view, but a good basic program can search through and recover deleted files even if the recycle bin has been emptied.
Everything you do can overwrite deleted files though, so if possible look for and download the undelete program on a laptop or another pc and keep your current one off until you're ready to try to save things.
Also have a flash drive ready to save the recovered files to. If you just save them back to your pc, then the recovered ones will overwrite the other deleted ones you are trying to save.
Tribal Prophet's onto something., but I have another idea:
-Get a good undelete or file recovery program and install it onto a removable HD, and use it to try to recover the files. Remember to save them to the portable HD.
Of course, and easier idea: if you're running a laptop, remove the HD, put it into an enclosure, and run it as a removeable on another computer; put the recovery program on the computer and save the files onto that computer. Also, it's probably a good idea to run an anti-virus scan on the drive while it's out of your computer.
As Tribal suggests, don't save the files to the HD where the files were. That's a bad idea :)