Efectivamente te han metido algo. No desesperes que casi todo tiene remedio.

Aparte de lo que has hecho, descargate el Spybot desde su pagina original (la primera que sale en el gxxgle al buscarlo) para evitar bajarte otra cosa que el bueno. Es shareware.
Instalalo y actualizalo para tener todos lo ultimos datos.
Inmuniza.
Pasa el escaneo para que el te quite lo que pueda, que sera la mayoria. Una vez que limpies todo vuelve a hacer escaneo, que algunos bichos se ocultan detras de otros hasta que te diga que esta todo limpio.
Esto te quitara los ad-awares, robots,malwares y otras hierbas.

Ponlo en modo experto (No te agobies que no es demasiado complicado de manejar) y mira que es lo que te aparece en inicio de sistema para quitar el bicho que se te autoarranque.

Entra en la pagina de Kaspersky que es un antivirus muy conocido que tiene un scanner on-line para revisarte el ordenador. Es una pagina .com, no .es
Te hara instalarte un par de activex en el proceso. Autorizale a hacerlo. Luego te instalara la base de datos, etc. La primera vez tarda unos minutos, pero las siguientes solo hace actualizaciones y es mas rapido.
Este scanner no matara ningun bicho pero es muy exhaustivo y encuentra practicamente todo y con el informe que te da puedes proceder a eliminar lo que tengas a mano o con programas específicos para cada bicho.

Suerte