Welcome to the ever growing problem of spyware, and it's #1 accomplice, Internet Explorer. Simple reality of the situation, is that the more you use Internet Explorer and/or Outlook Express, the more this is going to become a problem for you. Thankfully, there's a simple two step process to deal with it.
The first step is to download a copy of AdAware and Spybot. Make sure to update the both of them, then let each of them scan your system. You'll probably be amazed at the amount of garbage that's been put on your system without you even knowing it.
After you've let those programs clean up the problems you've already got, step two is preventing them from being able to come back. For that, you need to abandon all use of Internet Explorer and Outlook Express (except for visits to Windows Update). Download a copy of Firefox (and Thunderbird if you use Outlook Express) 1.0RC1. It should be able to import almost all IE settings for you on the first run, including bookmarks. Then you make Firefox (and Thunderbird) your default web browser (and Thunderbird for email) and pretend that IE doesn't exist. Since IE is at the root of probably 75% or better of all spyware infestations like yours, using a browser like Firefox cuts that route off at the knees. And might I suggest you investigate the AdBlock (http://adblock.mozdev.org) extension for Firefox. It is a life changing extension that allows you to filter out ads of all kinds. Banner ads, ads in frames, ads in the middle of an article, ads on the side of a page, flash ads, you name it. It lets you reclaim the space used by those ads, and at the same time blocks the browser from even downloading the ads, even if you aren't seeing them. It's one of those indespenible extensions, and there are plenty more.
And if for some reason Firefox isn't to your liking, you can always give Opera a try. But that's your only other option on Windows, because all other "browsers" are really IE at the core, and then you would have gained almost nothing.