I am not sure how related this is to exactly this problem. I am not using memcache (as far as I know), but if I use the cache plugin that comes with Joomla, captcha does not work on retry (refresh or subsequent attempts). What happens is that the text is regenerated, but the old image is presented. The user does not see the new image.
Is there a way of excluding captcha from cache?
I pulled this from joomla system info:
What php version? 5.2.13
what GD version? bundled (2.0.34 compatible)
what freetype version? 2.2.1