I'd agree with BRL, with the addition of:
9. Download and run HijackThis, post log here, wait for advice!
(Might look much better after 1..8, but best get a second opinion!)
Formatting your hard drive and reinstalling XP is a real last resort
(eg when XP won't boot, even in Safe Mode, thus can't get to 1
)
RC