Try Ad-aware as well as Spybot. Turn off system restore while you run full scans again!.
Try this online virus scan:
http://www.pandasoftware.com/actives..._principal.htm
And this online trojan scan:
http://www.windowsecurity.com/trojanscan/
Look in add/remove programs for anything that may be related to a Taskbar. This could include something like coolwebsearch etc.
Be carefull not to delete anything you need!.
Also look in your startup list in msconfig to see if there is anything in there that looks suspect.