Judging from your description in this post
you are most likely infected with CoolWebSearch Hijacker. There are many version and they are all a pain to get rid of. Those scans might work, but as often as not they don't.
Your best bet is to submit a HIjackThis log so we can see exactly what you have on you system and exactly how to fix it.
Follow the instructions in the following tutorial, post your log in the HJT forum, and we'll get you fixed up. How to post a HijackThis Log
And BTW, you should leave System Restore on until your system is clean. Turning it off before doing a scan won't fix your problem, just prevent your antivirus from yelling that you have some infected backups.
We always did feel the same
We just started from a different point of view
Tangled up in blue--Bob Dylan