Yep 128MB is definitely what you should consider in any but the rock bottom gfx cards. The 4200 did muddy things a little because the orig 4200_64MB used slightly faster RAM than the orig 4200_128MB BUT even when including o/c'ing in to it the 128MB cards was the better buy. Now you should find the 4200-8X_128MB uses the same higher clocks and faster (better o/c'ing) RAM so that's what you should go for if you do go nVidia. Rad8500LE/9100 if clocked at (or very close to) 250/250 offer excellent value as they aren't far off 4200 perf but really Rad9500PRO is supremely good value and a very lastable card.
EDIT: Forget the 9500PRO comment (which is accurate) but must have been intended for a previous thread, if you're considering 64MB cards you aren't likely to be in the market for a £150/$190 gfx card LOL!