A change in the production site affects test and staging sites and vice versa
What you're describing can happen when you link several sites up to the same cache system, but give the same prefix for each of them in settings.php (or don't provide a prefix at all, which is essentially the same thing).

I'm not 100% sure, but disabling the memcache module might not stop it being used if you're declaring its use in settings.php, which you most likely will be. 

It might not be the cause, but it definitely could result in exactly the situation you find yourself in. Check settings.php in each of the sites, and see what the state of those prefixes are. If this is the problem, providing different prefixes for each site will fix it straight away.