honestly go for something with 1gb of memory. 512mb is starting to show its limits. I have a 4870x2, and Farcry 2 at 1680x1050 with 4xAA 16xAF(Ultra High) eats up to 750-910mb of VRAM. Crysis also ate upwards to 900mb of Vram on the final boss (same settings)
Wowzers. What program are you using to monitor VRAM usage?