How did you delete everything off of the hard drive? I'm not so sure you actually got rid of the virus. Did you install the new OS from a burned copy, or from one that was bought? What anti-virus program did you use to verify that the virus was gone? I'd upgrade the RAM, and video card. The X1650Pro is a good choice, which was stated earlier, or you can get a HD2600XT. Although the X1650Pro is a great card, I wouldn't get the 64-bit version that was suggested, I would pick up a 128-bit version.
Diamond X1650Pro 256MB 128-bit $57 w/ free shipping.
Newegg.com - DIAMOND 1650AGP256T Radeon X1650PRO 256MB 128-bit GDDR2 AGP 4X/8X Video Card - Desktop Graphics / Video Cards
Powercolor X1650Pro 512MB 128-bit $50 ($40 after rebate)
Newegg.com - POWERCOLOR X1650PRO 512M AGP Radeon X1650PRO 512MB 128-bit GDDR2 AGP 8X Video Card - Desktop Graphics / Video Cards
Powercolor HD2600XT 512MB 128-bit $60 ($40 after rebate)
Newegg.com - POWERCOLOR HD2600XT 512M AGP Radeon HD 2600XT 512MB 128-bit GDDR2 AGP 4X/8X HDCP Ready Video Card - Desktop Graphics / Video Cards
As for the ram that was suggested, I would take full advantage of the 2GB kit. With the RAM upgrade and the graphics card upgrade, you're looking at spending around $100, which isn't a bad price to keep a 'dead/out-dated' computer going strong. I'm still running socket A.