Generating thumbnails when using a memcache server for session storage frequently signs users out
My solution to this was to swap memcache for Redis. I realize that doesn't resolve why memcache wasn't working for us, but swapping it corrected this issue.

My best guess is either:


We were caching data to memcache that was too large for it to optimally handle. 
Memcache was being overwhelmed when asked to cache the thumbnails for images that Craft was generating.


These are completely unfounded, but just some best guesses on what was happening.