When you search for deleted Word files are you able to preview the contents of the files in the Recover My Files preview window.
Recover My Files has very strong preview capabilities for Word docuemnts. So much so, that it can preview corrupt word documents that Word itself cannot open. This is probably the problem you are having. Please download the following free Word repair program,
http://download.getdata.com/wordrepair.zip and repair your files. You can also run this program in batch mode.