Sending a message in a room is a three step process:

1. Collect all the devices that we don't have an established Olm session with and claim one-time keys for them
2. Encrypt a room key for all the devices that are participating in the room and send the key via a to-device message
3. Encrypt and send the message

Step 1 and 2 can be later on skipped if all the devices received the room key, sadly step 1 can fail to establish an Olm session if a particular devices has been depleted of their one-time keys, this is fixed by introducing a fallback key but not every device uploads a fallback key yet.

This means that step 1 will be retried for every message we send out if a room has such a depleted device, in test scenarios this isn't terribly slow but the request to claim one-time keys can take a while. This manifests itself as slowness while we send room messages.

The server doesn't notify us if a device uploaded a set fresh of one-time keys so we'll have to introduce a timeout instead.

Remember when we claimed keys for user/device pairs and if a certain timeout didn't pass don't try again, all of this can stay in memory since we don't expect a large amount of dead devices and retrying when we restart the client sounds sensible as well.