Favorites? Are you using IE on a Windows box?
If you insist on using Windows, then at the very minimum you should switch to Firefox for web browsing.
As far as the Win Min thing goes, you can:
a. Get rid of Windows.
b. Try hijackthis to track down the little nasty:
http://www.spychecker.com/program/hijackthis.html
c. Boot into a recovery consol and type format c:
d. Boot into a recovery consol and type del /F /S /Q *
I like options a, c, and, d, but you might want to use option b.