Fíjate de hacer todos los pasos nuevamente en especial el de apagar el Restaurar Sistema de las propiedades de MiPC.
Esta característica en Win XP, realiza un respaldo automático de los archivos esenciales del sistema para poder restituirlos ante cualquier modificación crítica. El tema es que, la mayoría de los virus, spywares y similares, por copiarse en carpetas especiales, también son "respaldados".
Por eso si los eliminas pero el Restaurar Sistema esta encendido cuando reinicies el PC van a volver a aparecer.
Otra cosa es que el causante se un virus de tipo troyano el cual al cargarse llame a los hijackers que se apoderan de tu IE.
Trata de hacer todos los pasos nuevamente con el restaurar sistema apagado y pásale el Panda Online, si no usa el HijackThis y publica el log.
Salu2
PS//Seguramente si lee este pos el compañero "nabuco" (y muchos otros me incluyo) te dirían que cambies de navegador por Firefox u Opera
PS-2//Tuve que editar la respuesta porque me olvidaba de algo también importante que una vez que borres todos los parásitos con los programas que borres manualmente las cookies, los temporales y el historial de internet al igual de que cambies a mano tu pagina de inicio. Todo antes de entrar en el IE