Virus - The version of this file is not compatible with the version of windows you're running

I'm cleaning up a Windows 7 computer that was infected with malware. I pulled the HD out, hooked it up to my machine with a USB adapter and then scanned it with MalwareBytes which found (2) Trojan.FakeAlert files from C:\Users\%username%\AppData\Local\ and (1) Trojan.FakeAlert file from Temporary Internet Files. I went ahead and told Malwarebytes to remove the files which it did successfully.

The computer appears to run OK now except I can't get into anything without getting the following error message:
The version of this file is not compatible with the version of windows you're running. Check your computer's system information to see whether you need an x86 (32-bit) or x64 (64-bit) version of the program, and then contact the software publisher.

I get this error message when trying to use Regedit, Task Manager, Windows Update, System Restore, msconfig, Internet Explorer, Google Chrome, etc. It appears this problem affects all .exe files.

I should add that the error prevents the program from running.

How can I get rid of this error message and allow Windows programs to run normally? (Sorry I failed to put my question in right from the beginning.)

Edit1:
The names of the malware files removed are:
dpc.exe
vew.exe
download[1].exe

Edit2:
I've discovered that I can avoid the error message and make any program run normally by right clicking and choosing Run as Administrator. I'm currently downloading and installing MalwareBytes on this machine. I'm suspicious there might still be some malware running on this machine.

Edit3:
The symptoms have now changed slightly. If I double-click on Internet explorer I get the "Open With" window. If I choose Task Manager from the TaskBar right-click menu, I get an error message: Application Not Found I'm pretty sure this is a problem that can be corrected in the Windows Registry. I remember fixing this issue, or a similar one, on Windows XP but I don't remember anymore how I did it.

Answer

After you mentioned fixing this in XP before, you made me remember a reg file one of the other admins at my job keeps on his FTP. I have used it once on a users PC who was having the exact same issue as you (only he had xp) after I removed some malware. I figure I will post it here since it may help you out, even if it just points you in the right direction:

[HKEY_CLASSES_ROOT\.exe]
@="exefile"
"Content Type"="application/x-msdownload"
[HKEY_CLASSES_ROOT\.exe\PersistentHandler]
@="{098f2470-bae0-11cd-b579-08002b30bfeb}"
[HKEY_CLASSES_ROOT\exefile]
@="Application"
"EditFlags"=hex:38,07,00,00
"TileInfo"="prop:FileDescription;Company;FileVersion"
"InfoTip"="prop:FileDescription;Company;FileVersion;Create;Size"
[HKEY_CLASSES_ROOT\exefile\DefaultIcon]
@="%1"
[HKEY_CLASSES_ROOT\exefile\shell]
[HKEY_CLASSES_ROOT\exefile\shell\open]
"EditFlags"=hex:00,00,00,00
[HKEY_CLASSES_ROOT\exefile\shell\open\command]
@="\"%1\" %*"
[HKEY_CLASSES_ROOT\exefile\shell\runas]
[HKEY_CLASSES_ROOT\exefile\shell\runas\command]
@="\"%1\" %*"
[HKEY_CLASSES_ROOT\exefile\shellex]
[HKEY_CLASSES_ROOT\exefile\shellex\DropHandler]
@="{86C86720-42A0-1069-A2E8-08002B30309D}"
[HKEY_CLASSES_ROOT\exefile\shellex\PropertySheetHandlers]
[HKEY_CLASSES_ROOT\exefile\shellex\PropertySheetHandlers\PEAnalyser]
@="{09A63660-16F9-11d0-B1DF-004F56001CA7}"
[HKEY_CLASSES_ROOT\exefile\shellex\PropertySheetHandlers\PifProps]
@="{86F19A00-42A0-1069-A2E9-08002B30309D}"
[HKEY_CLASSES_ROOT\exefile\shellex\PropertySheetHandlers\ShimLayer Property Page]
@="{513D916F-2A8E-4F51-AEAB-0CBC76FB1AF8}"

If you want to try testing this back up HKEY_Classes_Root first, then paste the above text into notepad and save it as .reg then double click the file to import it. You made need to do it in safe mode. If it works for 7 please let me know!

UPDATE

I tried to import this key in an (ill advised) attempt at testing to make sure this wouldn't hose your PC. Windows 7 didn't take the file not really sure why... I don't have the time to look at it right now but I hope it at least points you towards the keys you should be looking at.