Hmmm, weird stuff. If you're using WinXP... you're right, IE is a core component, and not really uninstallable.
Maybe try flushing the TCP/IP stack with:
netsh int ip reset resetlog.txt
from a command prompt. It prolly won't work, it's kind of a Hail Mary.
My favorite resolve: Format and reinstall!