^That's a can of worms... the laptop I am currently using was bought nearly four years ago and has technically never been "reinstalled". The installation of Windows 7 was actually copied (by using GParted) to the SSD I bought and the Windows 8 installation it now runs was an "upgrade" of the windows 7 it originally came with. There are no problems, and the 8.1 upgrade fixed an occasional BSOD issue I had with 8.0 when resuming from standby. It's still as good as new in most respects.
You shouldn't need to rebuild every year, if you are due to problems then your usage habits need to be rectified. I work in IT, so I understand I'm the exception to the rule as common sense appears to be in short supply around computers.
With that said The Greenlander can most probably get rid of his problem by using HiJackThis to weed out the entries and then HitmanPro (free 30 day trial) or Combofix to blast away the remaining remnants.
Malware isn't a good thing to have just sitting on an OS, I would strongly advise against ignoring it.