Have you tried booting in safe mode? Try that, then disable anything set to run at windows boot in msconfig (start > run > type "msconfig" > ok).
That shit's in the registry, I generally delete it straight from regedit. Some malware also hides as a windows service so I'd suggest you look for suspicious entries in services management just in case.
Finally make sure your network settings weren't changed. A few months ago I had some malware change my DNS servers to some obscure ukranian server so all my traffic was being proxied through their servers.
Yeah I forgot. Try
SpyBot Search & Destroy, it does a lot of this automatically.
It took more than 5 minutes