A virus can't survive a true format and re-install unless your installation image is infect. Sometimes a virus can infect the MBR (master boot record) or other storage area. In some cases the "back up" data you take off might be infect and every time you finish re-installing you simply re-infect your system.

I believe they started including a command in the FORMAT command to "wipe" the entire drive by writing all 0's. I haven't really played with anything beyond XP/2003 server, but I swore I saw it the other day on someone's PC. Anyway, try that.

These viruses are created to avoid automatic detection and removal; so, using tools to remove them like that does not really work in this sophisticated day and age.