I actually agree with design choice #3: the authentication app should be tied to the phone and not the cloud account. Having to re-register your MFA app when yo

I actually agree with design choice #3: the authentication app should be tied to the phone and not the cloud account. Having to re-register your MFA app when you switch phones is exactly how I would design it too. There's a chicken-and-egg problem here when people don't have access to both the old and new phone at the same time (or, as you say, they do a factory wipe), but to me that only suggests they need a different recovery process, not leak the customer's MFA secrets to the cloud.