Some historic messages are undecryptable, but are loaded much later

[richvdh]

Sometimes, often when you scroll a long way up your timeline, you encounter occasional unable-to-decrypt messages. (Empirically, it seems like the further back you go, the more UTD messages you find.)

Often, if you come back later on, some of those UTD messages are decrypted.

When we look at the logs, we see:

• Decryption error
• Key retrieved from backup
• But no attempt to re-decrypt (until much later)

In other words, this sounds much the same as #3786, but it's intermittent.

[richvdh]

One suggestion was that the homeserver is overloaded with GET /room_keys requests, and starts rejecting them -- but this doesn't seem to be the case. As per the description, the keys appear to be successfully retrieved from backup; they just aren't used.

Another suggestion is that the keys are being retrieved from backup during the notification-sync-poll, and the main "thread" doesn't receive a memo that the key has been retrieved, making this similar to #4189. This seems incorrect given it affects quite old messages, though.