yea, some of these spyware/malware programs hide themselves in the registry such that they are nearly impossible to get rid of. One of the most common is coolwebsearch (and it's variants), you might try the cool web shredder program.
That one is the worst. I even had the coolwebsearch techs trying to help me get rid of it and couldn't.
I gave up on the box and transfered all my important files to a new PC.