Okay, this is really puzzling. Your ability to decrypt a message should not depend on whether the device was turned on when it was sent! Your device should not even know when a mail was sent until it downloads it from the server and reads the metadata (and it could totally download it a month after it was sent, that is normal).
It would be odd if this was a server problem, because you’d think someone else would have noticed it. You could add a profile with another server to check, but it’s a longshot.
Asking if the system clocks on both devices are correctly set is a bit of a longshot.
The most rational reason for the non-reception is that both devices are deleting mails from the server when they download them, even though you told them not to do that in the GUI. This explaination does not explain the undecrypted messages. Could they be overwriting the downloafed messages with corrupted versions? But that would imply a very odd design. Are all the messages that are undecrypted on one device decryped on the other?
Do you have a third device you could install to? This would let us see what is on the server.