APC/Memcache disables translations

When any form of caching is enabled in civicrm.settings.php that persists beyond the current HTTP request, the English version of all strings is shown instead of the translation.

When using ArrayCache or NoCache, translations work fine.
When APCcache or Memcache(d) is enabled, texts that have already been cached aren't translated - so over the course of a few requests, the interface is completely in English.
For instance, when calling /menu/rebuild the return page and popup notification are localized for that request only. From the next request on, the menu is cached and shown in English.
I suppose the translation step is skipped before saving the result or before displaying it.

I discovered this because I tried to set up Redis based on the current Memcache class. But it turns out to be a problem for all cache options.
Reproduced this in all recent versions (4.7, 4.6, 4.4).

I'm willing to help with a fix myself if necessary, but it would probably take me a few hours to find out exactly what happens when strings are fetched and cached. I'm hoping someone who is more familiar with the core code will see why and where this might occur a lot quicker.