Tu problema no creo que esté relacionado con las cookies. Sólo son archivos de texto, no pueden tener un virus. Lo que tienes es un spyware (un virus) que lo que hace es mostrarte publicidad mientras navegas.
Para eliminarlo yo te recomiendo Ad Aware que es gratuito y va muy bien:
http://www.portalprogramas.com/273-d...-Ad-Aware.html
Tienes otros anti spyware en:
http://www.portalprogramas.com/progr...i-spyware.html