This is normal for older messages on new devices (=client/app) due to how forward secrecy in OMEMO works. Once you add a new device you need to send a message from it for all devices to exchange the encryption keys for the new device. Afterwards all new messages should be en- & decrypted as expected.
Edit: if you use webclients they can sometimes lose the keys due to browser side privacy settings, so that might be another reason.