Desinstala el MSN, elimina el perfil de configuración (Documents and settings\\Microsoft\Messenger) o busca cualquier referencia al messenger en el disco duro y eliminala. Repasa con algún limpia registro (CCleaner) y vuelve a instalarlo.
Tampoco estaría mal que probases con otro cliente, para descartar; emesene, Pidgin, Miranda IM...