Alice getting a warning about key mismatch and a prompt for redelivery (or not) of the pending message. Bob-with-new-phone does not get to read Alice's messages to Bob without Alice at least having the ability to verify that Bob indeed changed phones. Yes, 99% of users will click "redeliver" without checking, but the ones for whom secrecy matters won't.

I think this is how Signal does it, and it is the only security conscious way to do it.