I have been experiencing much the same issue as above. I was infected with the Antivirus Pro 2009. I ran a virus sweeping software (Webroot Antivirus), after which I could no longer open most .exe files. This was all done while logged on at the office on the office domain. I brought the computer home with me and was planning to try the solutions that you suggested to others this morning. When I booted up the laptop, changing the domain to the local one for my computer set up by our former administrator, everything seems to work fine. But, I logged off & changed the domain to the office domain and the problem still exists. I am hesitant to make any changes without checking first to make sure that I am doing the right thing.
The operating system is XP.