How are old encrypted messages recovered for the sender? Take ProtonMail as an example. It encrypts all emails with some kind of asymmetric keys. But obviously, they can't store my private so the key must be obtained when I log in. This means, they must be able to generate the same key multiple times. I thought they used my password to deterministically generate the keys, but then I changed my password and I was still able to open my old emails. How is that possible?
Here is a way you can do it: use a key derived from the password to encrypt your long-term private key.


When you want to register an account with password $\mathit{pw}_0$:


Generate a key pair $(\mathit{sk}, \mathit{pk})$.
Generate a salt $s_0$.
Derive $k_0 = \operatorname{Argon2id}(\mathit{pw}_0, s_0)$.
Compute the ciphertext $c_0 = \operatorname{AES-GCM}_{k_0}(\mathit{sk})$.  (Set nonce = 0.)
Store $(\mathit{pk}, s_0, c_0)$.

When you want to read your mail:


Rederive $k_0 = \operatorname{Argon2id}(\mathit{pw}_0, s_0)$.
Decrypt $\mathit{sk} = \operatorname{AES-GCM}_{k_0}^{-1}(c_0)$ (or report authentication failure).
Use $\mathit{sk}$ to decrypt mail.

When you want to change your password to $\mathit{pw}_1$:


Rederive $k_0 = \operatorname{Argon2id}(\mathit{pw}_0, s_0)$.
Decrypt $\mathit{sk} = \operatorname{AES-GCM}_{k_0}^{-1}(c_0)$.
Generate a fresh salt $s_1$.
Derive $k_1 = \operatorname{Argon2id}(\mathit{pw}_1, s_1)$.
Compute the ciphertext $c_1 = \operatorname{AES-GCM}_{k_1}(\mathit{sk})$.
Replace $(\mathit{pk}, s_0, c_0)$ by $(\mathit{pk}, s_1, c_1)$ and erase all copies of $c_0$.



(This is presumably close to what ProtonMail does.)