Microsoft Authenticator: "Unable to recover - your backup is not stored with [account]" after factory reset

Hello,

I'm trying to restore Microsoft Authenticator from cloud backup after a factory reset, and the restore fails.

Setup

• Device: Huawei Mate 40 Pro, EMUI 13
• Authenticator version: 6.2609.6214
• Cloud backup was enabled for several years and linked to my personal Microsoft account (the only Microsoft account I have)
• I successfully restored from this backup several times before, most recently about a year ago, on the same phone with the same app

What I did

1. Performed a factory reset on the phone (same device, not a new one)
2. Installed Authenticator and chose the restore option right away
3. Signed in with my personal Microsoft account
4. Did not change my password, region or any other account settings beforehand

Expected result

Accounts are restored from the backup, as in previous restores.

Actual result

Sign-in succeeds and the restore progress screen appears, then it fails with:

"Unable to recover. Your backup is not stored with ******@live.com. Try signing in to a different personal Microsoft account."

Questions

1. Why would the app report that no backup exists for this account when backups worked for years? Is there a known cause, such as the backup being detached or deleted?
2. Can the Authenticator team check on the backend whether a backup exists for my account, or is linked to a different account ID?
3. If a backup exists, how can I restore it? If it doesn't, what are the options for recovering the accounts?

Account sign-in support redirected me to this forum and said the Authenticator team is the right contact. If a support ticket is needed instead, please tell me which channel to use.

I can provide any additional diagnostic information.

Thank you.