Serious issues with permissions (I think?)

Everytime I try to launch any .exe file, I get "Choose the program you want to use to open this..." dialog. I have a screen shot below of what I'm talking about. If I right click the .EXE file in question, and select "Run As..." and then just click OK on the next dialog window that open, the .EXE runs fine. I do NOT need to change anything in the "Run as..." dialog box; I just let it open, I click OK, it closes, and the .exe runs. It happens with everything; in the screenshot, you can see it's "cmd.exe" but it happens with mspaint.exe, or DialAFix.exe, anyfilename.exe.... I can get to a command prompt by right clicking cmd.exe and going the "Run as..." route, but I can't run sfc /scannow because the "Choose program to open with" comes up....
H E L P ! ! ! ! !

TYIA

 

Oh yeah.... I just got done removing a bunch of malware, and I think this is a result of that....

WinXP Home SP2