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 recipie

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.