When you do the search be sure to have the search include your whole computer.
This is usually listed under the "advanced search" option, and you select that option by selecting: Location/Everywhere
To do this: click Start menu, then Search... when the box opens click the Advanced Search arrow. This should open a box where you can be more specific about what and where you search... like I said; make sure you select the "Everwhere" option from the location tab and make the search term either something like: Beatles - Yesterday.mp3 (for a specific file you know you should have) or *.mp3 (star/dot/mp3) which should show the location of all your mp3 files.
I hope you can find your files... it would be really frustrating to lose so many songs all at once.
Good luck!