But did u format only the C drive (or the drive in wich the os was loaded) or the entire Hdd ?
Coz, as u said the virus problem still persists after the format, so im guessing that u didint format the entire hdd and hence the virus must hv migrated to another partition..
btw, use a better AV like NOD32 or Kaspersky or even AVG (any one of the 3 will do) to remove the virus, i knw its a tedious job to keep on recommending AVs, but they are the best in the business, so b4 u do a complete format, plz use these...
Also, use a registry cleaner like XP Tools Pro, to remove unwanted reg entries....

----------------
Cheers n e-peace...