In light of this my money is on a virus not a hardware issue. I know how much of a pain having to reformat your machine is (trust me done it multiple times during the early days of XP SP1 days.) but it may just be your machine is too infected and starting a fresh is the only way to know for sure you got it all. Good luck let us know how you get on.
This is most likely not a virus but a wrong setting in the registry for start up programs. Sort of like the "my documents" folder appearing at startup. Its just a matter of looking at the entries in Msconfig on the startup tab to determine what entry needs to be fixed, which usually just requires added quotation marks.