1 - Apaga "Restaurar Sistema".
Las entradas 010 - LSP puedes repararlas con la herramienta LSPFix
Manual de LSP-Fix - Winsock 2

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:\DOCUME~1\papa\CONFIG~1\Temp\se.dll/sp.html
R1 - HKLM\Software\Microsoft\Internet Explorer\Main,Search Bar = res://C:\DOCUME~1\papa\CONFIG~1\Temp\se.dll/sp.html

R3 - Default URLSearchHook is missing

O2 - BHO: (no name) - {ED95DF51-2B00-4479-AC1F-943BD1C88B39} - C:\WINDOWS\System32\hebp.dll

O4 - HKLM\..\Run: [sp] rundll32 C:\DOCUME~1\papa\CONFIG~1\Temp\se.dll,DllInstall

O9 - Extra button: Papelera - {072F3B8A-2DA2-40e2-B841-88899F240200} - C:\ARCHIVOS DE PROGRAMA\AGNITUM\OUTPOST FIREWALL 1.0\TRASH.EXE (file missing) (HKCU)
O9 - Extra 'Tools' menuitem: Papelera - {072F3B8A-2DA2-40e2-B841-88899F240200} - C:\ARCHIVOS DE PROGRAMA\AGNITUM\OUTPOST FIREWALL 1.0\TRASH.EXE (file missing) (HKCU)

O16 - DPF: Win32 Classes -

O16 - DPF: {11111111-1111-1111-1111-111111113457} - file://c:\ied_s7m.cab
O16 - DPF: {11111111-1111-1111-1111-511111113457} - file://c:\x.cab
O16 - DPF: {11111111-1111-1111-1111-511111113458} - file://c:\x.cab
O16 - DPF: {11311111-1111-1111-1111-111111111157} - file://C:\Recycled\Q678340.exe

O18 - Filter: text/html - {E86E3725-72F5-409B-BBEC-C29A9963BCB9} - C:\WINDOWS\System32\hebp.dll
O18 - Filter: text/plain - {E86E3725-72F5-409B-BBEC-C29A9963BCB9} - C:\WINDOWS\System32\hebp.dll

O20 - AppInit_DLLs: 5emdh861mub.dll

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

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.

Respecto a tu segunda pregunta: No es tan fácil denunciar esos casos, más que nada porque para ser efectivo tendría que denunciar mucha gente, tú sólo no representas "poder potencial" contra la gente que se dedica a fastidiarnos la vida de esa manera. Pero, una pregunta: ¿cúal es la página del antispyware que se te abre, y como se llama dicho antispyware que te pide que descargues?

Saludos.