MSN explorer debe ser fácil de eliminar, lo deduzco porque no lo tengo, luego no me dió trabajo. Lamentablemente, no recuerdo como lo hice. ¿seguro que no está en agregar/quitar programas? (previamente editando el archivo \windows\inf\sysdoc.inf y borrando todas las palabras "hide" que encuentres, sólo esas cuatro letras, que dejarán dos comas juntas).
Para Outlook Express, aquí hay información para desinstalarlo:
http://www.tweakxp.com/tweak2101.aspx
No lo citas, pero también pongo como desinstalar el windows messenger, por si acaso:
menú inicio -> ejecutar -> RunDll32 advpack.dll,LaunchINFSection %windir%\INF\msmsgs.inf,BLC.Remove
Otras inutilidades como el Movie Maker, WMP y IE son más delicadas de desinstalar, si es que se puede, y lo más probable es que eches a perder el sistema operativo. Mejor soportarlas con resignación.