Forgive me if this is too obvious, but you did look under “Microsoft Internet Explorer” and not just “Internet Explorer” in the Add/Remove list, right?
I wouldn’t try just deleting it…Windows is all wrapped up with the browser in some weird way and I think you’d do more harm than good.
One other small and useful trick: clear your cache. A couple hundred SDMB threads and forum lists, the graphics from a few dozen websites, etc., can clog it up to the point of seriously diminishing performance, especially on a dialup.
In MSIE go to the Tools menu, select Internet Options, and click on the “Remove Files” button in the middle of the page. There are other ways to access this: Start, Settings, Control Panel, Internet Options is one.