Aqui te dejo una captura de como desistalarlo:

PD: Tambien puedes usar el programa
zapmessenger que lo que hace es desistalartelo por completo sin dejar rastro y despues lo vuelves a instalar asi suele funcionar.
ZapMessenger es una utilidad para erradicar cualquier rastro del paso de MSN Messenger, Windows Messenger y Windows Live Messenger de tu ordenador.
ZapMessenger elimina los ya nombrados programas de mensajería de Microsoft así como su información de instalación. Su principal utilidad radica en la solución de problemas en la instalación de alguna versión de Messenger.
Después de pasar ZapMessenger por tu PC, éste quedará limpio para realizar una instalación desde cero de Messenger.
Requisitos mínimos: NET Framework 3.5
El Programa Es Totalmente Gratuito.