I don't know how computer literate you are, but there are a few things to try before you go the wipe your computer step. Download Adaware (from
www.lavasoft.de) and Spybot (google search) Update both of them. Also download a program called "Hijack This"
Scan with Adaware and then with Spybot to see what you find. This should clear most problems from your computer. Occasionally one of these will find things that it can't fix but at least you know what the problem is. Run HijackThis, be careful and follow the instructions, and save a logfile. Now. Restart your computer and repeat.
If Adaware and Spybot can't fix it, and you're not very computer literate, take the newest Hijackthis Logfile and find a computer help website and post it. Almost every computer help website wants this before they help you. (you can also PM me with it or post it here if you like) Someone else can then point out what looks wrong on your logfile.
If you are comfortable with the computer, go through the Hijack This scan results. Look for things that don't make sense...
What this problem sounds like is Cool Web Search or a variant. The thing is a bastard when it comes to trying to remove it and it required registry edits. Once you nail down the problem, a google search can point you to tools to try and fix it. PM me if you have any questions!