Formatting is your cure-all, however, there are other methods you may want to consider:
Remove the hard disk from the computer and put in another. Scan the hell out of it with Antivirus/AntiSpyware software etc. Once "cleaned" put it back.
The lazy man fix: Remove the disk and discard it. Purchase a new one and windows xp/ vista / whatever OS. Have some store install it for you.
Some tips:
If you care about the contents of the disk, then back it up. I.E. copy the entire contents to another disk.
If you have one virus, there's likely alot more. However, mention the name(s) if you know them and perhaps some people ont his forum can help you out with the specifics.
Facts: Viruses are created every day. This is the reason companies are constantly providing updates to their software (daily downloads of virus definitions). Yes, it's entirely possible a virus can have "no cure;" this can be for numerous reasons, but just because something has no cure today doesn't mean it wont tomorrow. Although I've never seen this happen, I've heard of a virus that can infect your BIOS, which is kinda like RAM, but keeps computer information/settings in it when the computer is turned off. Other parts of the computer like the CPU/RAM/capacitors/Cards/etc. cannot be infected, just disks.