issues with object cache (memcached as backend) and wpmu when flush_all is run

Are you running WordPress 3.5? If not, you should try upgrading because the stability of the blog-switching functionality has been greatly improved in this version:

Multisite’s switch_to_blog() is now significantly faster and more reliable

Once you have done this, try using the trunk version of the Memcached Object Cache plugin which adds support for the new blog-switching performance enhancements in WordPress 3.5:

Add support for wp_cache_switch_to_blog().

We were experiencing similar problems with switch_to_blog() and Memcached Object Cache in WordPress 3.4, and making the above changes resolved the problems in our case.