You are right, we don't and can't know if any of what Meta says is true, but at least on the surface it seems to check out. If they are stealing your private key and unlocking all your chats in secret, then they are doing a bloody good job, since no one has leaked anything yet.

Just to clear things a bit, in your analogy you don't hand the courier both the chest and the key. The chest has a special keypad that accepts two keys, one is your key, the other is the recipient's key. What you do is you lock the chest with your key and then give it to the courier, which will deliver the chest to the other party, which will then open the chest with his key. In theory the courier never had access to the key.

Now the issues are that you are indeed writing your message from within the Whatsapp building and you can never know if there cameras watching you or not. You also cannot know if Whatsapp has made a copy of your key, or the recipient's key without your knowledge.

As for how can you recover all your chat history even after you destroy your phone, it's quite easy and Whatsapp doesn't need to know anything in particular. The functionality allows you to make a backup and store it on Google Drive. That backup gets encrypted with your password and it's probably the most secure thing of all, if nothing else because Meta would gain nothing from the backup having poor security (as it would already have all the data if they wanted it) while it would only make them loose face, plus would allow anyone else to gain access to all ~~your ~~their data. After you restore the backup on a new device a new key+padlock pair gets created and the lock gets shared to all your contacts (which will see the yellow box telling them your padlock has changed).

I'm not claiming it doesn't have privacy issues mind you, I'm just saying that you can't be sure either way, unfortunately. Still, better than Telegram that doesn't even encrypt most of your chats.