I think you want to look more at core clock, etc. If you are running lower resolutions probably not a big deal, but if you want to run high resolution, etc. Then you need to look at memory. But if all things are equal, I don't think it'd be a bad idea to have the 512 mb instead of 256. But like for me, I low-med resolutions, and even though I'm probably going to get the 8500 gt, yea, everyone says bad for gaming I know, I am probably going to order the one with 600 mhz core clock and ddr3 memory vs regular 450 mhz core and ddr2 memory. My point? Watch what you buy, look at speeds on core and memory, like I could get an 8500 with 512 mb of ddr2 memory, but I'm going for the other b/c I think ddr3 will make the speed a little faster overall, even with only ddr2.
Have you looked at the ATI radeon 2900 gt's? Or the ATI 2600XT? Should be comparable to that 8600 you want, and you can get one with 512 of ddr3 memory for 114.99. Might be something to consider. Maybe even look at the ATI 3800 series if your will to spend about 150 or a little above. Just some ideas.