... a mi me aparecían cosas como esas pero en el ICQ (uf!, que tiempos) e incluso con Yahoo. Esos suelen ser asuntos de la red, aunque igual posiblemente sea algún virus, busca info al respecto.
Por cierto, yo prefiero Kopete
(de momento, solo para Linux) ... que igual un tiempo podía conectarse a Skype, no sé de otro mensajero que lo permita.
Edit:
Un bonito bot ..
http://www.dreamnotoftoday.com/?p=1334
Como dije, es asunto de la red, no es tu compu ni un virus en ella. En los comentarios hablan de una opción del MSN para no permitir mensajes de personas que no estén en tu lista de contactos, busca en las opciones del Pidgin algo similar (Kopete lo tiene).