You have run the right type of search. If you dont get the file names back (check both file and folder view of the Recover My Files search results screen) then unfortunately they have been destroyed.
The file and folder names are stored in a separate place on the hard disk to the actual file data. One can be destroyed by not the other.
You can use "Mass Renamer", avaialble at
http://www.getdata.com/download.php to rename the Word and Excel files. You may also like to try Explorer View from
www.explorerview.com - use Explorer View and the F2 key in Windows Explorer to rename the files.
I hope this helps.