Because you have up-to-date virus protection, they may not have been able to alter your registry. Perhaps there is an exe file somewhere that you missed.
If you would like us to take a look, you can run Hijack This from the link below (a quick start page with more info and instructions).
Create and copy a log and paste it here.
http://www.tomcoyote.org/hjt/