ratbastid, just a hunch here, but i would run all your usual spyware programs after cleaning all the cookies and crap and then try a third party registry tool to search for invalid references. If something's in the registry, it might find a way to reappear when windows is restarted.This one works well for me using xp. it's called regseeker.
http://www.hoverdesk.net/freeware.htm