iexplore.exe isn't a critical component of windows... you're thinking of explorer.exe's shell integration with windows native web-browsing abilities.
Go to c:\windows\system32\dllcache (you might have to type it into your address bar at the top of any window), scroll down and delete iexplore.exe (it's just a backup in case the "real" iexplore.exe gets deleted).
The go to c:\program files\internet explorer and delete iexplore.exe . XP will popup saying OMG CRITICAL FILE DELETAGE OH NOES >_<!!
So, choose not to replace the files, and now IE isn't present on your system.
Explorer.exe/the Windows kernel do have some of the web surfing functions built into each window (address bar, search, bookmarked sites/folders, etc.), but Windows does not REQUIRE Internet Explorer installed.
As has been said, you probably had spyware or your IE was horribly bugged.