Does the warning name the spyware involved?
If Microsoft Antispyware hasn't taken care of this when you've restarted in
safe mode and done a full, deep scan, I'd recommend looking further.
If you do a google search on toolbar.dll symantec, the first two hits show
different spyware which use this .dll file. You can check those two
articles and see whether their manual removal steps (or, if you are lucky,
an automated removal tool) help.
Alternatively, Trend Micro's online antivirus scanner now detects and
removes spyware--so it might be worth trying:
http://housecall.trendmicro.com