After trying to remove IE from my XP box I have finally found a solution!
Do a search for IEXPLORE.EXE and let the search include hidden and system files and you will (typically) find 3 instances. They will be in the program files folder, a folder called presomething and some other blue cloured folder. Delete them all.
Windows will bring up a dialog box asking to insert the windows XP cd but just click cancel and it goes away
Also remove MSN messenger by entering the following command into the Start >> Run command
[EDIT:: Added information]
All browsing around the computer stuff works fine.
[ August 07, 2002: Message edited by: smokey mcp0t / b0b ]