Thanks guys. I believe I've fixed the issue here:
This is really difficult to reproduce. In order for it to happen:
1) cache has to be set up correctly
2) cookies cleared (or first ever request to the site)
3) the form page being viewed then submitted needs to trigger a cache *miss* - so the error would only occur once every X minutes at most, where X minutes it the cache expiry.
If anyone's able to verify that the above fix resolves this issue for them, that would be a great help. It's a bit hard to rely on the demo site for verifying the fix (I have deployed it to there nonetheless) since it's dependant on the timing of a cache miss. So on your own site the easiest steps to reproduce, with cache set up correctly:
1) clear cookies (or incognito mode with chrome)
2) delete everything from the site's cache (I use the file based cached which makes this easy, just delete the local cache directory, I guess you could restart memcache too)
3) load a page with a form on it, and submit it
If you can try those steps both before and after the above fix, you should be able to consistently reproduce the error, and then see it resolved when running again the fix.