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.