When this happens, it means that the client actually is unable to decrypt the messages, and can do nothing about it if it can't obtain the keys somehow.
You have 3 options to fix it.
I'll assume you're on android.
The best is to go through with verifying your device. Then your other devices - those which have the encryption keys, the server doesn't and that's the point - will send all the keys they have to your new phone.
If you don't have those devices, but you have set up secure backup,
then the server actually has all your keys for safekeeping, but they are encrypted with a password that you provided (this is separate from the login password).
In this case you should be able to restore the keys by verifying your new device that way. It happens through the same dialog.
It's very, very recommend to set up secure backup, for everyone.
The third option is that if you have exported your encryption keys in the past, you can import them back manually. This is kind of the same as the automatic key backup, but this is stored where you choose instead of your homeserver, and it's not being made automatically.
Your can use the same menu for exporting and importing this way that.
If you don't see a banner asking you to verify your device, all 3 can be done in the "security & privacy" menu of the settings.