No, no tienes (no tendrías) que formatear. A mí se me solucionó así, pero seguro que no es la única solución.
A veces, ciertos programas instalan complementos basura (como barras para navegadores, motores de búsqueda, programas de iconos o power-ups del Messenger o incluso aplicaciones chorras e innecesarias del Facebook), y a veces tenemos programas de "dudosa reputación", que instalamos para casos puntuales y luego nos los dejamos olvidados...
Una buena limpieza a fondo del ordenador, aparte del antivirus y del antiespías, con un programa específico para malware y desinstalando cosas que no sirvan y/o pasando programas como Ccleaner puede que sirva de algo.
Intenta, temporalmente, dejar de usar el Messenger. Es decir, no solo no iniciar sesión, sino cerrar completamente el programa. Contacta por otras vías con las personas que te avisaron y pídeles que hagan una especie de seguimiento. Si con esta medida el problema se reduce o desaparece, ya tienes el foco de entrada detectado y podrás buscar más información de una forma más eficaz... o plantearte usar otro cliente.
Espero haberte ayudado, aunque solo haya sido mínimamente :(
