“can’t guarantee the authenticity of this message” just means it was restored from backup. In the same vein, if you can decrypt a message in any client, it should upload the keys to the message backup so it can be decrypted on other clients, even ones that haven’t logged in.