DB, have you tried the recently opened file list within Excel ? This is in the File menu - saves the last 4-6 workbooks opened previously.
EDIT - I see you tried Search - might want to check Advanced Options.
Here is how to search using Windows Explorer:
Open your My Computer icon and click the Search button or hold CTL button and tap E (CTL + E). Click Search for All Files and Folders on the left.
For file name type *.xls and choose your drive. Might want to click the Advanced Options and make sure "search sub-folders" and "Search hidden files and folders" and search "System folders" are all checked then click Search.
If no files are found and a search of your other hard drives (D: or E: or __: ) also returns nothing - you have another option in System Restore.
Go to All Programs > Accessories > System Tools > System Restore. Choose a date prior to the data loss and see if this helps. You can always undo the restoration if it does not help and if you do find your missing files, back them up, then for good measure undo the System Restore just performed.
Good Luck !