Scot Bickell I do not have a solution to get you in sooner but wanted to note a couple things that may help others. I am also the Admin but my org is only 4 E3 users (and three are me). I recently upgraded my iPhone 12 to a 14 and restored they iPhone from the cloud. All my MS Authenticator items were there (I did not have to restore from backup) but the E3 365 items in Authenticator I had to log back into each account security (on computer) and re-scan the barcode for the MFA. My MS Live accounts all I had to do was log in on MS Authenticator. All my other non MS accounts were there.
To login to my 365 accounts I think I chose the SMS option when prompted since the Authenticator was not setup on that phone. I think I used my LastPass authenticator code on one to try it. I do have second android phone I could have used for he prompt but chose not to. I also have Last Pass Authenticator on the iPhone. Now that one you can restore all the accounts on the new phone and that still worked for the 365 accounts. The LastPass app was not properly restored from the iPhone cloud backup restore. I uninstalled it and restored the backup. I guess the MS Authenticator is different due to the push and the iCloud backup did not fully restore the E3 accounts. I already read about that so was prepared.
One question I do have on MS Authenticator backups. If I backup MS Authenticator on my iPhone to a MS Live Account and backup the one on my android to the same MS Live account, will that create an issue? I wound up creating a second MS Live account just to backup the android since I did not want to mess up the backup on the iPhone.