Primero, para ir descartando, borra todo el perfil (perderás todos los emoticonos, guiños y toda esa chorradita guardada):
c:\Documents and Settings\\Configuración local\Datos de programa\Microsoft\Messenger < borras completamente la carpeta Messenger
(nota, la carpeta estará oculta, activa la opción de mostrar archivos y carpetas ocultos)
Desinstala el Messenger, dale un repaso con una utilidad de limpieza de registro (CCleaner) y reinicia. Vuelve a instalarlo a ver que pasa.
¿Tienes instalada alguna chorradita como el MSN Plus! y derivados?. También puede esa ser la causa de los problemas.