Hola, sigue estos pasos:

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\system32\gxfwn.dll/sp.html#37049
R1 - HKCU\Software\Microsoft\Internet Explorer\Main,Search Page = res://C:\WINDOWS\system32\gxfwn.dll/sp.html#37049

R1 - HKLM\Software\Microsoft\Internet Explorer\Main,Default_Search_URL = res://C:\WINDOWS\system32\gxfwn.dll/sp.html#37049
R1 - HKLM\Software\Microsoft\Internet Explorer\Main,Search Bar = res://C:\WINDOWS\system32\gxfwn.dll/sp.html#37049
R1 - HKLM\Software\Microsoft\Internet Explorer\Main,Search Page = res://C:\WINDOWS\system32\gxfwn.dll/sp.html#37049
R1 - HKCU\Software\Microsoft\Internet Explorer\Search,SearchAssistant = res://C:\WINDOWS\system32\gxfwn.dll/sp.html#37049
R0 - HKLM\Software\Microsoft\Internet Explorer\Search,SearchAssistant = res://C:\WINDOWS\system32\gxfwn.dll/sp.html#37049
R0 - HKLM\Software\Microsoft\Internet Explorer\Search,CustomizeSearch = www.terra.es
R0 - HKLM\Software\Microsoft\Internet Explorer\Main,Local Page = www.terra.es

R3 - Default URLSearchHook is missing

O2 - BHO: Class - {6193F353-3FEC-F33C-C485-636D47657206} - C:\WINDOWS\system32\appmi.dll

O2 - BHO: Class - {F55BC142-6DAC-87A2-D58A-4ADF205AA1D3} - C:\WINDOWS\system32\iekq32.dll

O4 - HKLM\..\Run: [PS2] C:\WINDOWS\system32\ps2.exe

O4 - HKLM\..\Run: [iesi32.exe] C:\WINDOWS\system32\iesi32.exe

O4 - HKLM\..\Run: [apiwx32.exe] C:\WINDOWS\apiwx32.exe
O4 - HKLM\..\Run: [mfceh32.exe] C:\WINDOWS\system32\mfceh32.exe

Y TODAS las entradas que he marcado en tu log en negrita.

3 - Localiza y elimina (usa KillBox si es necesario):

C:\WINDOWS\system32\mfceh32.exe
C:\WINDOWS\system32\ps2.exe
C:\WINDOWS\apiwx32.exe
C:\WINDOWS\system32\iesi32.exe
C:\WINDOWS\system32\iekq32.dll
C:\WINDOWS\system32\appmi.dll
C:\WINDOWS\system32\gxfwn.dll

Y todos los ficheros asociados a las entradas en negrita que te indiqué eliminar en el paso 2.

4 - Luego limpia el registro con un programa como RegSeeker por ejemplo.

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

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

7 - Reinicia y nos cuentas los resultados.

Saludos.