I agree that decrypt/encrypt is bad—it is simply not E2EE. The solution would have to be a better method of public key distribution for ‘federated’ systems.

While I don’t know anything specific about facebook messenger, E2EE doesn’t necessarily preclude what you suggest. A messaging service could store the entire chat history encrypted without decryption keys. When you get a new client you could restore the entire history in encrypted form onto your device. You would then use a recovery key you would possess to decrypt the message history on your end. At no time would the messaging service have the keys to decrypt. I’m not saying that is what facebook does.