Two mutually verified users can not read each other's messages

**Describe the bug**
Two users on my homeserver are using the latest iOS Element client (1.0.16) and have verified each other's devices. Each of these two users has one and only one device. Both users have shown me screenshots showing that the other's device is verified from their perspective. And yet frequently these users are not able to properly see each other's messages, with the

```
** Unable to decrypt: The sender's session has not sent us the keys for this message. **
```

placeholder text appearing in the place of the other's message. It appears that some messages become visible after a while (hours) and sometimes messages are visible immediately, but usually they cannot read each other's messages.

**To Reproduce**
As mentioned above, both clients are using the latest iOS Element client available in the Apple App Store (1.0.16) at the time of this writing. Both users have verified each other's devices. We are running Synapse 1.21.2

**Expected behavior**
I expect that two users sending messages from mutually verified devices should be able to see each other's messages at all times without ever seeing the `** Unable to decrypt` placeholder text.

**Aditional context**
Other users on this homeserver are using the Linux desktop client or Android mobile clients (various versions, downloaded from f-droid). These users are able to read the messages of both users without problems.

The server is behind Cloudflare, with custom rules so that nothing is cached for the subdomain the matrix server lives on.