Lookup and insert newly generated keys in cache

If the key is not in the keycache or keycache update takes
a while we might not find the key in the ::key() method. This
leads to bugs.

BUG: 386506