Habrias de comprobar en el registro que programas arrancan con windows.
Por cierto si tu acceso a internet depende de algo que tengas que instalar (un CD que viniera con el modem o algo asi) reinstala dicho software.
otra cosa es que si pasaste varios antispyware puede que tengas algunos instalados todavia, y de ahy el problema, no hagas mezclas, si puedes instalar esos programas solo para pasarlos de tanto en tanto mejor, mientras deja solo una suite de seguridad (antivirus+firewall+etcs) y nada mas, y desinstala todos esos antyspy y otros de seguridad que no sean la suite de seguridad principal.
PD: Despues de todo lo dicho pasale el ccleaner, y siempre con estas cosas haz reinicios despues de limpiezas y cosas similares.