How do I find out that my recipient has a new device/public key that they'd like me to encrypt with?

If it's because Apple tells me so then I think can see that the end to end encryption is broken and interception is possible.

Are old messages re-encrypted with the new key?

This would be even worse.

iMessage does not allow for any out-of-band key verification. It's correct that that Apple (and anyone compromising them) is in a position to change the recipient's key or add new ones without the sender noticing anything's going on. I think iMessage limits this to new messages. (I believe syncing is done through iCloud, which doesn't use E2E-crypto but is optional.)

It would still be possible to implement this in a secure way (including out-of-band key verification) by having the "original" key (the one you've compared out-of-band) sign keys for new devices and have the server deliver that signature (which the sender can then verify). I don't know if there are any implementations of this.

The hard part is how do you manage a list of trusted devices.

The thing which is really sad is that there are no end to end encrypted group chats.

https://riot.im is doing this.

e2e is in beta still, but they have key list management/verification in place already.

> The thing which is really sad is that there are no end to end encrypted group chats.

In iMessage specifically, or in general? WhatsApp/Signal do use E2E-crypto for group chats.