Answer
This question was answered on November 26, 2005.
Much of the information contained herein may have changed since posting.
Try using this helpful utility: ToolBarCop
And /or the manual registry fix: (backup the registry first)
Start Registry Editor (Regedit.exe)
Go to the following location and check each GUID sub-key, one of which is the malware toolbar entry:
HKEY_LOCAL_MACHINE\Software\Microsoft\Internet Explorer\Extensions
Also check this sub-key:
HKEY_CURRENT_USER\Software\Microsoft\Internet Explorer\Extensions
(check the values in the right-pane to identify the malware toolbar.)
Once you find the correct entry, delete the appropriate key.
Once again, remember to back-up teh registry and your my documents before trying these fixes.