Removing IE from Windows isn't a piece of cake, as you've discovered by now. When you uninstalled it in the add/remove control panel, I expect you merely uninstalled the recently-released IE7, which just rolled you back to IE6.
Prior to Windows XP, you could physically remove IE from a computer (though it wasn't always easy), but with XP, to satisfy various antitrust rulings, Microsoft changed this while making it easy to "disable" IE without actually removing any of the files it uses. Why? Because all sorts of programs and OS functions use various pieces of IE. Deleting the files that comprise it, as you mentioned late in your message, is actually quite dangerous to your computer's stability.
If you want a minimal trace of IE on your machine, go into the Add or Remove Programs control panel and click on "Add/Remove Windows Components," on the left side of the screen. Scroll down to Internet Explorer and uncheck it. (It will say the option is 0KB in size; this is normal, since, as described above, you aren't deleting any actual files, just making them invisible as a web browsing system. See screenshot for how this looks.) After this, IE won't show up in any menus or on your desktop, and it won't ever launch as a web browser. (You can still use IE Tab if you need IE's rendering system. To reinstall IE, just reverse the process above and recheck the box.)
That said, I just leave IE intact and tell Firefox to be my default web browser. That option is in Firefox under Tools > Options > Main tab. At the bottom make sure the option "Always check to see if Firefox is the default browser on startup" is checked. Frankly, I wouldn't bother worrying much about IE as long as you never have to actually use it...
