Con desinstalarlo desde "agregar o quitar programas" solo quitas los accesos directos al mismo. No al internet explorer.
Para que no te comas mucho la olla... la unica forma de desinstalar completamente el explorer del windows, es... desinstalando windows. Es un componente interno que usa, por ejemplo, para enseñarte el contenido de una carpeta de tu disco duro.
El msn messenger lo que hace es llamar directamente al explorer (pasando de cualquier eleccion tuya de navegador, y eso, creo que no se puede cambiar).
Si quieres, prueba el aMsn, que te permite definir con que navegador abres los enlaces y demas. (si mal no recuerdo, no lo uso).
Saludos
....
