You might want to stop over at the
HijackThis Forum and post a HJT log. This wreaks of malware but it could be other things. See if they give you a clean bill of health and if they do then it may be caused by other things.
Also, I don't recommend that if you attempt to re-install Windows you do it from inside Windows. Things are smoother if you boot from the XP CD, Format and Erace the Hard Drive and start fresh. Like I said, though, have them check out your HJT log and see if that turns up anything.
BMR777