This was what brought MS down in Europe in the case against them a few years ago.
Short of instilling the Beta copy of IE7 which is available here
http://tinyurl.com/3ykut
I don't think that there is much that you can do as it's a required component to download any MS Patches through the Windows Live Update Program.
IE is just totally integrated into the Windows Kernel and has been that way for a long time now.
Even on Business machines that will never be connected to the Internet I always just remove the shortcuts to IE from the start menu and run like that. When a Internet Browser is required we use Fire Fox and have never had a problem with that getting into any sites, even the Microsoft ones except for the Live Update Site where IE is required.
Also remember that IE and Outlook Express are the same program so you need to remove both to have any chance to remove IE from the system. That may be of some help when you attack the Registry as you'll need to delete any references to Outlook Express as well as IE.
Personally I've never had a problem going anywhere with FF except as stated the Windows Live Update site and I go to MS Tech-net using FF only so if that was going to present a problem I would have thought that it would there. About the only place that I can think of that would require IE is a site that is attempting to exploit IE to break into Windows by causing a Buffer Overflow and they are places that you would normally want to avoid like the plague anyway.
But if you would like to site some examples I'll have a look see. But I'll be using a Nix Distro with FF as a first option to look just so that I can make sure that it's safe and then I'll try a installed Linux running IE to see what happens.
Col