I've got some bug on my computer that neither the spyware nor virus
programs seem to be able to remove (everytime I boot up, I get a small
window that says "Antivirus report - Is your computer infect with spyware?";
then when I open Explorer, I'm misdirected to some bogus search engine).

Try Spybot Search & Destroy before reformatting (ugh)... It might find the spyware that is causing your suffering and eliminate it...
http://www.safer-networking.org/en/index.html

Hope it helps!

Cheers,

Miguel