Not sure how to replicate this apart from leaving it running on a large multisite install, but after so long some blogs start redirecting to other blogs on visit, i.e. when you visit subdomain1.blog.com it will go to blog.com instead. Disabling the object-cache.php fixes it, so it's definitely that.
This is using the latest version of the Memcached object-cache.php and WordPress. I will also say that we are using multisite networks split into 3 different sub-networks, not sure if that will have an impact, but only one physical WordPress install uses the object-cache.php and Memcached server, it's not shared with anything else.
The APC object cache used to do the same thing, but we are on a multiple server set up now so can't test that anymore. Although using APC object-cache used to improve the speed of WordPress throughout, the Memcached one seems to add 300ms-10s to the loading time of pages, especially the admin area.
If anyone could shed any light on the situation I'd be grateful.