I've noticed this with Windows NT varients; i.e. 2k and XP.
'95, '98 and ME seem to be less vulnerable to 'push'-viruses (Mainly because they don't have all that crap running in the background.)
On the other hand, you usually end up installing 9x every 10months, whereas once you install 2k/XP, you ought to never need to install it again, unless you upgrade something big like your motherboard, or do something stupid like running as Administrator all the time and clicking on Bonzai Buddy links...
But it's definitely recommended that if you HAVE to re-install 2k/XP, you make a slip-streamed CD with the service pack of your choice, and then download ALL the hot-fixes and patches for that version and burn the whole lot to a CD.
Disconnect your compy from the network BEFORE you zap the whole system, hard reboot and install.
If you don't mind installing something as kludgy as ZoneAlarm, it's a good idea to get that up ASAP too.
Luckily none of my computers connect directly to the 'net; They all go through my DSL router which make is harder for such virusses to get in.
2k and XP are real dog's 'tho - I had to do a reinstall of 2k once, but found my slipstreamed CD had been snapped in half (!), so I took out the network cable, installed it, then disabled as many services as I could to try and stop any virusses getting in.
Plugged back into the network and went to windowsupdate, but then I found it wouldn't work until I enabled a whole load of services.
I did that, and BAM, within 5 minutes I had that "NTAUTHORITY-blah-blah-Shutting down in 30 seconds" dialog, which usually means Blaster/Sasser has just ****ed your OS up the arse.
In the end I had to boot up Knoppix and download all the patches manually (Do you have ANY idea how hard that is from Linux?! It seems to work at first glance but when you actually try and do anything... blek...)