spyware que no se elimina

Alguien me puede ayudar?
Tengo un spyware en el ordenador, que me lo detecta el anti-spyware de mi antivirus, y no consigo eliminarlo.

He intentado todo, incluso he formateado y he eliminado la particion existente creando una nueva, y aun asi, segun arranco el ordenador aparece.

Con el spyware me deja eliminarlo pero en cuanto reinicio vuelve a aparecer.

Si a alguien se le ocurre que hacer, por favor que me lo diga.

Gracias

Tengo windows XP con todos los parches de seguridad de microsoft instalados.
yo cuanto tengo algun spyware que me toca muxo las bolas lo que hago es ir al modo a prueba de fallos paso el ad-aware pro 6 (es el que tengo yo) y luego el disk cleaner, reinicio y paso el ad-aware y el spyware ya no ta
¿¿Has probado el Spy Bot Search And Destroy??

salu2.
lo de iniciar a prueba de fallos ya lo intente y tampoco consegui eliminarlo, sigue apareciendo, intentare lo segundo, pero se agradecen mas ideas por si acaso tampoco funcionara esto.
Gracias a los dos
3 respuestas