Congrats...you've been infected! It sounds like you are a victim of a drive-by-download, where adware/spyware was installed on your computer without your consent. I'd try the following:
* Check add/remove programs and see if the searchbar and any other "mystery" software is listed. It's rarely that easy, but you might just get lucky.
* Open Internet Explorer and go tools->internet options. On the "general" tab, select "delete cookies" and then "delete files." Then click "settings" followed by "view files" and delete anything else remaining. Finally, empty for TEMP folder (it's "local drive:\Documents and Settings\username\Local Settings\Temp" in Windows XP). I've found that some of the "nicer" adware/spyware can be removed by simply emptying these folders.
* Download and run other antispyware/adware applications, as a single program won't catch everything. I'd recommend Adaware, Microsoft Antispyware (if you have Windows 2000/XP), and Spyware Doctor, in addition to running another full scan with SpyBot.
* Make sure you have Antivirus software and a Firewall running no matter what. You said you had Norton Internet security installed, but didn't mention replacing it with another product. I started out with Norton, moved on to McAfee, and finally ended up learning a valuable lesson...free is better! Avast Antivirus 4.0 Home and ZoneAlarm Personal Firewall (basic) are both free, and have proven to be better than either McAfee or Norton. Then, for even more protection/features, you can purchase their Professional versions. I have been much happier with both their protection and use of system resources than I was with the "big name" products.
Hope this helps,
John
P.S. If you provide the name of the toolbar (if available) or the website it leads you to, we may be able to provide instructions on how to remove that specific invader.
This happens all the time on my laptop but not on my desktop computer. I use Firefox on both, and virtually never use IE. In fact, the laptop is newer (bought since I switched to Firefox) and we've hardly ever used IE on it EVER, except for a very few times when a site wouldn't work in Firefox.
Here's what happens: (and it happens whether I've got Firefox open or not) I get pop-ups, but the pop-ups are IE windows, even though Firefox is the default browser. They come up anytime the internet connection is open, even when Firefox isn't running.
Here's what I've tried in an effort to make this go away: I opened IE and installed the Google toolbar because I remembered the pop-up blocker that comes with it seemed to work well way back before I switched to Firefox. I also went into the Internet Options and disabled any kind of scripting I could find, and also followed instructions I found in an article on c-net to manage add-ons. Disabling scripts seems to make the content of the pop-ups invisible -- the windows are now completely white, at least most of them, but I don't want them coming up at all. They interrupt what I'm doing and sometimes make me lose keystrokes if I'm not paying close attention.
One note: IE on this laptop has some sort of search bar with dating and other similar links on it, which I did NOT install. If you try to uninstall it, you are taken to a website where you're supposed to download the uninstaller. I was suspicious of that so I didn't do it, but I wonder if this toolbar is somehow related to the problem.
I also ran Spybot search & destroy: that was pretty much no help at all. It found some stuff but deleting them didn't make the pop-ups go away. Recently I discovered the Yahoo toolbar has a Firefox option and I downloaded that -- it has an anti-spy option. That seemed to help, but only temporarily. I seem to need to run it at least every day, and sometimes twice a day. Not only that, but at least once in the few days I've had it, I've had to reinstall it in order to get it to work.
I am careful about what I download and I still get spyware, I just seems to jump onto the computer without my having to do a thing. I have to be careful, because this laptop only has 256 mb RAM. I try to really minimize running memory-resident software, or I'm constantly geting out of memory erors. I had Norton Internet Security running, but I finally uninstalled it. It doesn't ever find a virus (I rarely get a virus, I get other things like spyware), half the time it can't uninstall the adware/spyware it does find, it doesn't do anything to help with pop-ups, and the anti-spam wasn't working as well as the anti-spam that comes with Thunderbird, so I didn't really see that it was helping and it was a real memory hog. I also disabled the Tea-timer that comes with Spybot for the same reason.
Any ideas about how to address this problem would be grately appreciated! Thanks!

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic