Al final despues de pasar por tercera vez el Spybot search&Destroy me solucionó el problema. Creo que estaba relacionado con haber instalado el MSN PLUS, que me empezó a entrar publicidad por todos los lados, en el momento de desinstalarlo te da la opción de quitarle la publicidad y así lo hice. Asi que muchas gracias a todos y os dejo esto aqui por si a alguien le pasa lo mismo alguna vez.
Saludos
