well memory does make a reasonable difference at higher resolutions, especially if you want to play with bump mapping, high quality textures and all the other candy. i know for a fact quake 4 will start on Ultra Quality without 512mb, it just doesn't play so well at 1600x1200
i haven't tried at a lower resolution. i guess if you are looking at a decent card and you have the extra 20 pounds then you should go for it. if you don't have the money to spare and you won't in the foreseeable future you may as well get the card you can afford. just know that in general gameplay 512mb doesn't make it faster, only in circumstances where 256mb of memory can't cope does that become a factor.