Inicia en modo a prueba de errores y desinstala el messenger directamente. Luego pásale el regcleaner (para quitar del registro entradas inválidas debidas a instalaciones y desinstalaciones) e inicia después de todo esto normalmente.
NOTA: el Regcleaner lo puedes bajar de aki:
http://regcleaner.softonic.com/ie/11891