estuve en tu misma situacion hace meses.. probe nod, kaspersky, norton... y una infinidad mas. (los removal tools tambien)
me cargaba todos los procesos del administrador de tareas, en plan "windows pelao pelao"... pero seguia ahi.
formateé, y nada mas arrancar windows por primera vez, al conectar a internet volvia a salir el cartelito, como si el virus fuera internet, vamos xD
volvi a formatear, con el router apagado, y todo iba bien.. hasta que encendia el router y salia el cartelito xD
total, mi solucion, y con la que estoy muy muy muy contento, fue linux
supongo que si no te apetece liarte con linux, de poco te servira mi mensaje...
suerte, y si consigues arreglarlo, postealo, aun me interesa.