Ok, well so far I have not found a program that will attempt to recover the original file name. I have deleted MP3's but when the file recovery program finds them they are randomly named. This is really disapointing.
Fast File undelete as far as I can see does not have a search funtion on it which makes it not that good. Also it I'm not sure how it is supposed to work, the file I deleted was on th e root of C:. When I used it, I selected root and it showed files and folders that were on th e C: drive but it did not show any mp3, not even an oddly named one. then I went to the recycle bin and did not see it there either.
Then I used recuva and althought in the past I have been able to recover MP3's in testing it, it did not find any MP3 file at all. Then I tried unerase and it did not find an MP3 either, now one thing that might be causing this is that I copied the mp3 from the C: drive to another part of the c: drive then deleted the copy, I wonder if there is a difference in doing this then copying a file from one partition to another.
Search and recover so far doesn't seem very good, it came up with like 6 files on the c: drive so now I'm doing a sector scan which is going to take a long time to see if it can find anything more. It didn't even finish the sector scan and now it seems the program is not responding which is nice especially since this program only gives you 4 or 5 uses as a demo.
I'm testing out handy recovery on another computer right now, the first analize was able to find the badly named MP3, there is an advanced scan with handy recovery that takes a very very very long time, it's still going and when it's done I'm going to see if it can get the original file name from the mp3.
Update, so far the only program that I have tried that was ever able to get the original file name back has been file scavenger. However it seems that it doesn't take too long for the file name to be lost even though it seems the file may be intact. Are there any better programs anyone can recomend as far as recovering the original file name?