I believe the 64meg Ti4200s overclock better than the 128meg versions and the same goes for the 128meg versions of the FX5600s compaired to the 256meg versions. So if you look at it that way, it looks like the lower mem versions do overclock better.
As for AGP4x vs. 8x, there is a slight performance gain, but it's very slim. For me, going from an Abit BE7(4x) to an Abit Ai7(8x) with a Radeon 9800pro, it got me about 150-200 onions more in '03 @stock.
Back in the days of the ti4200 the 64mb version of the cards usually had the better faster ram. Back then it was not worth spending extra money on the extra ram. These days I would say get the 128mb version for some of the newer games.