Hola supercoco2000
No necesitas formatear la maquina lo que te esta afectando no es ni virus ni troyano sino algo que se llama spyware o adware lo que te recomiendo es que bajes de
www.download.com el programa de Spy Sweeper de webroot este programita es el mejor que e visto.
Espero que esto te ayude.
P.S.
No todo lo soluciona el Firewall necesitas bajar todas las actualizaciones de windos que salgan.