> Is there something I'm missing that makes this a hard problem?
Yes. Pretty much the entire security model of Signal underpinned by this UX compromise. The way signal works at the moment, you sign up for an account with your phone number, your device generates a secret, and that secret is used to secure all your communication. You can pass that secret around devices (as long as you have a device that has it - or just the original phone, I can’t remember). You are also responsible for making sure the people you talk to are really who they say they are. When you first add a contact, it’s up to you to make sure they’re not an imposter, and if they have to reset their account their secret changes, and you have to verify who they are again. If somebody takes over their phone number on a new device, they have to generate a new secret, and while they may succeed in impersonating the person (depending on how vigilant their contacts are), they at least won’t get access to the message history.
To allow for recovery of message history, you have to escrow the secret somewhere. If you give it to the service provider, then the security model is thrown out the window, and you just invented FB Messenger. If you give it to the user to escrow, then you’ve just kicked the can down the road, because a consumer is just as likely to lose a secret as they are their device, and the ways they may choose to store it will make the whole system less secure for essentially no UX gain.
This is an unavoidable trade off. If you want the service provider to be able to recover your account, then they (or at least somebody in addition to you) has to have access to your secret. If you want your messages to be private, then you can’t allow for a 3rd party to be able to recover your account.