I think this is a nameserver problem. My girlfriend's parents' computer did this, too, and there was an entry in the registry which I needed to change in order to fix it. Obviously, the problem originated from some type of malware changing the registry, but after that, it doesn't require a program to continue running. What happens is that the request for a website is sent to the malicious nameserver, which returns its own malicious IP. The address is then scanned for certain information (e.g. Google search information), and if it finds anything relevant, it redirects the user to their own ad-riddled site; otherwise, it redirects them to the originally-intended site. Obviously, this is a security issue in that all information you are transmitting is going through a malicious site. I would recommend trying to do something about this problem ASAP, even if it involves re-installing the OS.