Phone was updated from the latest stable riot-android to element via GPlay (no beta subscription)
Now all messages in all e2ee direct chats including new messages are: Waiting for this message, this may take a while.
After update the phone was verified via pitcture sequence with riot-web.
All contacts are verified and has green point/shield on all devices, all contacts are on my own synapse instance (1.15.1-1 debian stable).

Cross-signing is enables, Keys are trusted, Private keys are not known:

I tried to clear cache and to restart phone without sucess.
Trying to re-verify (Secure Backup -> Set up on this device) this phone gives:
via QR code both devices shows error:

via image set the phone shows:

riot-web says:
Verify other session
Verification cancelled
You cancelled verification. Start verification again from the notification.
[Clear]
Restoring messages from backup decrypts all messages. Newly received messages after backup recovery are shown as Waiting for this message, this may take a while. Restoring messages from backup again decrypts all messages, even just received before this restore.
Is any update there? It's completely impossible to use Element after upgrade!
Right now, after restoring messages from backup it says:
Cross-Signing is enabled
Private Keys on device
But still shows new messages as Waiting for this message, this may take a while
I know someone who also gets the Waiting for this message, this may take a while message a lot. It can take several hours for the messages to resolve but they eventually do.
Nothing has changed after more than a week of waiting, so I had to reinstall Element.
My parents have the same issue when talking between them. They do resolve after 24 hours or more, but of course that makes it impossible to have a proper conversation. Please give this issue some priority, beside the vague text it's more than just an UX bug!
Hello, can you please give more information on the element version of both devices?
Also could you check the security settings on both devices (is Encrypt to verified session only is ON?)

Do you have other sessions?
The fact that key backup import is able to decrypt could mean that your other session are getting the keys and uploading them to backup.
So it could be possible that your device is not getting the keys.
Go to settings > Advanced > and enable developper mode, this will allow you to see more about the error, if you go back to the room, what do you see for the errors?
Did you submit some rageshake (top righ button in home screen > report bug; add reference to issue #1607 ?
Speaking for my parents here, as I don't have this issue myself.
They use the latest version from the Google Play store, so whatever version that is. They don't have "Encrypt to verified session only" on.
They have other sessions, for both a tablet and a laptop (so webbrowser) at least.
I'll ask them to enable developer mode and submit a rageshake. Thanks for looking in to it!
element version
the latest available on GPlay
Encrypt to verified session only is OFF.
have other sessions?
Yes.
A few users on my server have reported this issue to me. Seems like this is still happening. Any news on workarounds/solutions?
It happened to me today after I cleared cache on Element installed on Android phone. I use Element 1.0.9[40100092]. In developer mode message says that sender's device didn't send keys. Before I cleared cache those messages were properly decrypted. I have 4 sessions (3x Firefox and one phone - the issue affected phone only), 2 of them are open and devices that were used sent affected messages are also on so at very least they should resent needed keys.
I don't have cross signing enabled. I verify all session manually.
Here on matrix-synapse-py3 1.22.1 (server), a user on the android client (update 19 Oct 2020) reported the same problem.
"Waiting for this message, this might take a while" for all the messages from a particular user starting at some date in e2e encrypted channels. The user with the bug can still receive messages from other users on the same channels.
A user just reported me this issue on the matrix.org server.
Have the same issue from time to time with different users (and some small group chats).
This did not happen with 1.0.8 and earlier (all from F-Droid)
All accounts on matrix.org.
Getting this for the first time today. Didn't change anything and was working fine yesterday. Encrypt to verified sessions only is off.

I'm getting this one a newly activated device after I did the cross-sign verification (Element Android 1.0.11 [40100112] (G-b847)).
My wife also runs into this bug on her Element installation on Android (Play Store). There is a strange behavior: As long as she stays at home connected to Wifi network, the issue does not appear. But as soon as the smartphone is using mobile LTE internet, it happened several times that I received these messages from her which never got decrypted.
Indeed @smeyersdev, I observed the same behaviour sporadically on poor quality connections. It appears to be related to instability of the connection.
Most helpful comment
My parents have the same issue when talking between them. They do resolve after 24 hours or more, but of course that makes it impossible to have a proper conversation. Please give this issue some priority, beside the vague text it's more than just an UX bug!