I know this might seem like a weird question, but just scan all the cd's you install software with after formatting the drive. I'm sure there are some sites that would do free scans... or maybe you have another hard drive with scanning software on you can make search the formatted drive? You might find you have a problem there... and if so, at least you know whats causing it. A hard drive, even though it doesn't actally delete data after formatting, should not have nay memory that it is there to cause any harm, and so no viruses/spyware should remain.
Hope this helps