I would try several things.
1) boot into safe mode and try run a scan there because safe mode loads only essential drivers and programs which means the virus may not load at all which gives you a chance to kill it before it starts mayhem.
2) try a system restore back to a time where i knew that my machine was clean. Run a scan then and ensure that what ever it was that infected my pc doesn't do so again. I'd also ensure that i scan system restore points and back up copies to ensure i removed the virus.
3) google the virus to see what registry keys it changes to see what it does and where it does it. Once i know this then i will go to those registry keys and delete them or change their to values to make the virus useless so it can be removed by AV software.
i feel that doing a full format or partition just to remove one piece of malware is a little extreme. You could always do a repair install on top of your existing os without losing data or trying the steps as above.
anyone else have any other ideas?