My rule of thumb is if you want/need to Crossfire, then get 1GB, if not 512MB is mostly enough.
If you don't Crossfire, by the time you reach resolutions high enough to max the 512MB (except for GTA4), the FPS will probably make it unplayable anyway. Then, if you want to play at high resolutions, you will need Crossfire, but the higher memory used would limit you if you only have 512MB.