Applications are being opened by IE instead of running normally

Solution 1:

Armed with addtional information you've given me via chat:
Unfortunately it does seem that your PC may get somehow infected with malware. As an example, This thread does look very similar to your problems

Malware or not, root cause of your problems probably lay in this little known registry gem - originally thought to allow easy debbuging: (source)

To setup an application to launch the debugger automatically

Start the Registry Editor (regedit).
In the Registry Editor, open the HKEY_LOCAL_MACHINE folder.
Navigate to HKEY_LOCAL_MACHINE\Software\Microsoft\Windows NT\currentversion\image file execution options.
Under the Image File Execution Options folder, locate the name of the application you want to debug (myapp.exe, for example). If you cannot find the application you want to debug:
    Right-click the Image File Execution Options folder and choose New Key from the shortcut menu.
    Right-click the new key and choose Rename from the shortcut menu.
    Edit the key name to the name of your application, for example, myapp.exe.
Right-click the myapp.exe folder and choose New String Value from the shortcut menu.
Right-click the new string value and choose Rename from the shortcut menu.
Change the name to debugger.
Right-click the new string value and choose Modify from the shortcut menu.

The Edit String dialog box appears.
In the Value data box, type devenv /debugexe.
Click OK.
From the Registry menu, choose Exit. 

Problem being you could (and malware does) put any executable as debugger, effectively running program of your choice instead of original target.
I was able to replicate your PC behavior adding Firefox.exe key with a debugger target of Iexplore.exe
To check if that's what affect you, open registry editor, navigate to HKEY_LOCAL_MACHINE\Software\Microsoft\Windows NT\currentversion\image file execution options and look for Firefox.exe and similar entries for programs exhibiting this behavior. Rename any suspicious keys to something else (eg. Firefox.exe bad) and re-run the app.

Last but not least - analyze those keys - maybe it will give you a hint of what was the source - and run a thorough scan of your system with a different tool than the one you have installed (if possible - with windows offline)

Edit: Sysinternals Autoruns (http://technet.microsoft.com/en-us/sysinternals/bb963902.aspx) comes in handy in checking image hijacks (among many other nice features). Download the tool, run it and unselect Hide Windows Entries in Filter options, then select Image Hijacks:

You may then either simply delete the entry or analyze it further using several options.
There is also a command line version, autorunsc. autorunsc -h prints image hijacks. Use autorunsc -? to see all options.

Solution 2:

New answer: Try this: http://www.dougknox.com/xp/fileassoc/xp_exe_fix.zip

or otherwise:

1. Open Registry Editor, then navigate to the following key: HKEY_CLASSES_ROOT\exefile\shell\open\command
2. Double-click the (Default) value in the right pane.
3. Delete the current value data, and then type: "%1" %* (ie., quote-percent-one-quote-space-percent-asterisk.)
4. Navigate to: HKEY_CLASSES_ROOT.exe
5. In the right-pane, set Data of (default) to exefile

Exit the Registry Editor.

Hopefully, this solution helps.

Source: http://windowsxp.mvps.org/exefile.htm

PS: It dangerous to simulate this problem, so please keep trying & don't give up... :)