OK lets see if something put a regkey in to block iexplorer from running

In the registry see if you have this
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Image File Execution Options\iexplorer.exe
and do you have anything under
HKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft\Windows\safer\codeidentifiers\
and
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Group Policy Objects\
Let me know what you find, feel free to export those keys and post them so I can look at them

(If you post them make sure to put them in a zip file)
Shane