Sounds like a problem one of my housemates had earlier this year, they caught some malware that deleted the file association for *.exe.
There was a trick I employed to force-open RegEdit (I think if you create a *.reg file on the desktop you can invoke the RegEdit process that way) where I then re-set the HKCR\exefile entry.
You'll want to reset the following keys/values (unescape as necessary):
exefile\(Default) = "Application"
exefile\EditFlags = 38 07 00 00
exefile\shell\open\command\(Default) = "\"%1\" %*"