1 - Apaga "Restaurar Sistema".

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

R1 - HKCU\Software\Microsoft\Internet Explorer\Main,Search Bar = res://C:\WINDOWS\TEMP\se.dll/sp.html
R1 - HKLM\Software\Microsoft\Internet Explorer\Main,Search Bar = res://C:\WINDOWS\TEMP\se.dll/sp.html

O2 - BHO: Explorer Class - {962F12AE-2773-4BEB-99EA-B5C3AB9A6606} - C:\WINDOWS\SYSTEM\DSMANA~1.DLL
O2 - BHO: (no name) - {5710EAAF-903E-4FF7-899C-E86D81BC2E84} - C:\WINDOWS\SYSTEM\KHJA.DLL

O4 - HKLM\..\Run: [sp] rundll32 C:\WINDOWS\TEMP\SE.DLL,DllInstall
O4 - HKLM\..\Run: [loader32] C:\WINDOWS\LOADER32.EXE

O18 - Filter: text/html - {80921CD5-23E0-4AA6-BDC8-60500E5F450B} - C:\WINDOWS\SYSTEM\KHJA.DLL
O18 - Filter: text/plain - {80921CD5-23E0-4AA6-BDC8-60500E5F450B} - C:\WINDOWS\SYSTEM\KHJA.DLL

3 - Luego limpia el registro con un programa como RegSeeker por ejemplo.
Tienes el "W32/Kol", asi que localiza el fichero:
C:\WINDOWS\Loader32.exe, y lo eliminas.

Luego accede al registro y borra esta cadena:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\Curr entVersion\Run
"Dynamic Link Library loader"="C:\WINDOWS\Loader32.exe". Para acceder al registro acude a "Inicio" >> "Ejecutar" >> regedit.

4 - Reinicia en "Modo a prueba de fallos" o "Modo seguro" y escanea el equipo con Ad-Aware SE, Spybot Search&Destroy y CWShredder; ya que tienes una variante del CoolWebSearch.

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

6 - Reinicia y nos cuentas los resultados.

NOTA: No olvides ACTUALIZAR el navegador de internet de inmediato, o bien instalar el Mozilla Firefox.

Saludos.