There are two possibilities here:
- You didn't do a true format
- The virus found its way into the kernel files
Either way, the only way to truly be sure that it won't come back on the next install is to run a program like DBAN and truly format the drive.
Windows' definition of a format is removing the File Allocation Tables... the directory of where the files are. This doesn't actually remove anything, it only 'turns a blind eye' to its existence, allowing it to be written over.
The problem you're going to have is that you DBAN will only wipe entire drives. If you have data on different partitions, DBAN only sees the drive and will wipe it all.
Now, the question you need to ask is; how important is it to me that I get this off my PC?
I would get an external drive, or large USB... anything you can store that data on for the time being. Boot up DBAN and wipe that drive clean. Re-install Windows (WITHOUT AN INTERNET CONNECTION!!!) and immediately put some AV software on there. Connect to the internet and immediately update Windows/Drivers/etc. Update your AV software and then connect the USB and scan it.
On my desktop, I just went through this entire process, only to get another, much more vicious virus only a few days after the rebuild... so I know how frustrating this is. Sucks that I now have to go through the entire process again, but I'd much rather the NSA be the only people spying on me, not joe schmoe who wrote some code.