Wonder if there are instructions for manual removal of Internet Explorer.
Here, try this:
Download & install
RegSeeker and click "Installed applications>Add/Remove Applications"
Before running RegSeeker, turn off System Restore by (right-mouse click) "My Computer>Properties>System Restore and click the button "Turn off System Restore on all drives".
Use the "Ctrl" button and the left-mouse button to select the Internet Explorer Entry(ies) to remove and then right-mouse button click "Delete selected Items".
Shut down & restart machine and verify they are gone (or not) in add/remove.
If this fails, we should start looking for manual removal of IE instructions.