1) Don't worry about the 512MB of memory on a video card. Be more concerned with pipes & core clocks. That extra 256 on the card isn't going to make that big of a difference.
2) Upgrade your comp's RAM to at least 1GB. That'll help with games, and other stuff, quite a bit.
3) I take it your system is AGP? Hell, for $200 you should be able to get in the low 7 series cards and if you can, they beat the 6 series all to hell. Maybe like a 7300 or 7600, if they make 'em in AGP, which I belive they do.
Edit: Look at these... http://www.newegg.com/Product/Produc...82E16814143046