The file names are stored in a different location to the actual file data. The file names are in table at the start of the disk called the Master File Table (MFT). Each file MFT record points to the location on the disk where the file data is stored.
When you run a "Complete Format Recover", select the new drive letter and search for the default selected file types. At the end of the search the old file system will be rebuilt and displayed in "Folder View" of the results screen. Check to see if you can find the full file and folder names here.
If you cannot, it means that the MFT records are corrupt, and they are no longer pointing to the correct location on the disk for each file. Recover My Files is smart enough to realize this (not like the other programs :-) ).
The reason that you get files without their file and folder names is because RMF can find the file by its unique header and footer, but because there is no MFT record there is no original name.
If it turns out that the names are destroyed, you can also try
www.explorerview.com (use Windows Explorer and the F2 key to rename files) or
www.123renamer.com.