1 - Apaga "Restaurar Sistema".

2 - Con todos los programas cerrados, ejecuta HijackThis, marca las siguientes entradas y haces FIX:

R0 - HKCU\Software\Microsoft\Internet Explorer\Main,Start Page = http://www.lordoftherings.net/

O4 - HKLM\..\Run: [Sin Espias] "C:\Archivos de programa\SinEspias\no-spy.exe" /autorun

O4 - Startup: Reboot.exe

3 - Luego limpia el registro con un programa como RegSeeker por ejemplo.
Desinstala el "SinEspías", no sirve de mucho.

4 - Reinicia en "Modo a prueba de fallos" o "Modo seguro" y escanea el equipo con Ad-Aware SE y Spybot Search&Destroy.

5 - Usa el Disk Cleaner para limpiar cookies y temporales.

6 - Reinicia y nos cuentas los resultados.
Nota: Tampoco estaría de más que se defragmentara el disco duro, la lentitud no siempre tiene porqué achacarse a problemas con spyware o virus.

Saludos.