Como se vê, nossa questão foi uma falha de tempestade de cache, como a falta de debandada.
Nós resolvemos isso implementando uma expiração de 50% do cache. Basicamente, para cada item no memcache, criamos um segundo item de cache com uma chave semelhante, mais a string 'regenerate' anexada. Esse item expira em exatamente 50% do tempo de expiração do cache típico, indicando à próxima solicitação que estamos chegando mais perto do cache expirado e a próxima solicitação precisará tentar regenerar o cache.
Isso evita a tempestade de usuários tentando regenerar o cache ao mesmo tempo e garante que o nosso cache tenha a melhor chance de permanecer sempre atualizado!
Um complicado para rastrear!