Wow, this has been a problem for over 2 years? I also have about 80 accounts for which Microsoft Authenticator is now broken. Dashlane and LastPass have ZERO problems. Google Authenticator has ZERO problems. Authy, zero problems.
Which app is a preposterous POS? Microsoft Authenticator. Microsoft's concept of a "backup" is a list of broken accounts? Absurd.
I would go farther and say Microsoft Authenticator is a trap. It tricks you into putting accounts into a POS which will become a future time vampire. How many of its users have discovered its backup is not a backup?
Your MFA codes backup is literally garbage with Microsoft--let that sink in. Your backup of your MFA codes is not sufficient to recover your keys--think again about what this really means.
Get Google Authenticator or literally any other product and never Microsoft. Lesson learned.