Por lo que decis parece ser que ese troyano esta en el MBR, por eso al formatear el HD no se elimina, hay 2 soluciones para ese tipo de infección:
1: reescribir el MBR, ésta opción es bastante jodida ya que un simple error o corte de energia te podría hacer perder la capacidad de booteo del HD y la tabla de particiones, no la recomiendo a menos que ya lo hayas hecho antes.
2: la mas fácil... bajate el F-PROT y buscate algun tutorial en google que está lleno ;) arrancas desde el diskette que te hace el F-PROT en modo texto (ms-dos) y ahi lo corrés al antivirus y listo, casi seguro solucionas tu problema!
PD: eso si.... hagas lo que hagas antes de pasar cualkier antivirus DESHABILITA TU CONEXON A INTERNET, ya sea sacando el cable o apagando el modem o como sea.
Saludos y mucha suerte!