There's no way to fix this. They're simply not XLS files. Simply rename "Project Management_Risk Control Matrix_Testing_Client_Back up Desktop.xls" to test.jpg and you'll see what I mean.
With file system based undelete, a recovery tool finds a reference to a file with 'not in use' flag, complete with file name and in case of NTFS the cluster runs. However, there is no guarantee the clusters pointed to haven't been used to store new data. In which case the file is recovered with original filename and all, but with different data. So, as original data is no in the file, it can not be repaired either.
Anyway, this is kinda typical for deleted file recovery, some files can be opened, others not. You mention you shut the system down. if you mean Windows shut down then plenty may have been written to the disk during shutting Windows down.
With original disk (f not used since deletion) you can do an other attempt to recover the files, try to carve them or something. Unless someone else has a bright idea I see no other solutions.