running high resolutions and antialiasing increases the need for video ram. id say 25x16 counts as "high"...so....if you want to avoid texture thrashing and other stuttery problems, get moar vid ram
This is probably the most informative thing I've ever seen on the topic. WoW with no antialiasing shouldn't be a problem, but with AA and/or a game with higher resource requirements, you could easily push it past 512MB.
Minimum 1GB these days. 512 is alright but it won't cut it in future games with high amounts of anti-aliasing/resolutions. You'll set yourself up for stuttering/jitters later on. You'll hate it when it happens.