And if Apple's servers lie to you and tell you there's a device with a private key they generated?

They may never have your private key, but you are still trusting them to deliver the correct public keys to other users.