Just be aware that the backup and restore on the Microsoft Authenticator is fundamentally broken for IT Admin use. The backup will only work for up to around 60 accounts before it just stops backing up. There is no fix or workaround for this, Microsoft has been aware of it for years and has done nothing. There needs to be either the ability to back up hundreds or even thousands of accounts, either automatically or a one off dump to OneDrive (business) or the ability to do a direct transfer from one device to another like Google Authenticator can do. I have been forced to maintain a second device and duplicate MFA registration on each of them rather than risk losing access to every account I have added in the past 18m.
A BIT of I.T.,
While trying to determine how to properly fix this problem for my earlier post i this thread, I ran into this Entra Blog article that details how the back and restore processes work, though I don't immediately see anything about a limit.
How it works: Backup and restore for Microsoft Authenticator | Microsoft Community Hub
Maybe something in the article will stand out to you, though it's possible this issue is really just some sort of either timeout or capacity limit relating to whatever they're using within the Google Android or iPhone iChain backup storage.
You didn't mention which type of phone you're using, since I'd guess it's probable the issue is related to a characteristic of that particular device's storage limitations. This is probably one of the reasons I've noticed that they don't even seem to recommend trying to backup and restore for individual users and instead suggest simply resetting their MFA setting to allow setting that up again.
They'll likely run into this problem even worse with the new passkey addition to the Authenticator, so I'm guessing they'll have to fix this problem there even for many consumers, since its very similar to the TOTP Key backup requirements.
Rob