The Complete File Search if finding the files based on their header and footer, which is why they have names called "Recovered....".
The documents on the disk sound like they have been slightly corrupted.
For slightly corrupt files our preview function for Word documents in Recover My Files is actually better than Word itself, which is why we can preview the contents of some files which Word itself cannot open.
To open the problem files, go to
http://www.repairmyword.com and use this progam to get access to the contents.
When you use the Complete Format Recover you are usign the File Allocation Table at the start of the disk to find the files. The FAT may be slightly corrupt, but still try opening these files with Word Repair.