Hi Sweet,
Make sure you have checked for updates before running your spyware/malware
removal tools, so that you are sure they have the most uptodate lists.
Failing that the Yahoo toolbar hijacks the IE SearchHook (and it appears
that something else has hijacked the Yahoo searchHook)
First up you need to disable the Yahoo toolbar. Tools>Internet Options -
Advanced tab - uncheck 'Enable third-party browser extensions'
Download and save the registry fix from
http://www.iecustomizer.com/?url=SearchHookFixDownload.asp
and run it to apply the registry changes...
This should fix the search hijacking, but if you re-enable the Yahoo toolbar
it will install its own searchhook and you may be back to square-one.
However even though you have disabled the yahoo toolbar the search
preferences for the Yahoo Search Provider should still be intact.
Regards.