Because of what has happened to your drive it looks like the File Allocation Table at the start of your drive has been completely screwed around. This is the table that holds all the file name and folder name information, so it is very unlikely given the results of your first search that you will ever get a meaningful file and folder structure back.
Probably your only option now is to run a "Complete File Search" of the drive for specific file types. This search finds files by using their unique header/structure/footer - but will not get the file or folder names. Yes, this is a real pain, no there is not much you can do about it.
You may also have a problem with fragmentation - although again it is difficult to say what state you files were in the the defrag problem happened. Obviously if the a file is in multiple parts over you disk then searching for the header/content/footer is not going to help.
There are some file renaming tools that may help for certain file types, such as "123renamer" (search Google for this), or you may try Explorer View for Windows Explorer from
http://www.explorerview.com which you can use in Windows Explorer to play and rename the important files (use the F2 shortcut key to rename files).