Si, a veces una vez que la PC se infecta (como comentabas tu), es dificil recuperarla sana del todo...
Realmente si ya probaste con anti-spyware y anti-virus, no se si te quedan muchas cosas por probar...
Aunque ten en cuenta de que siempre está la opción: