Microsoft Authenticator backup not recognized by the same recovery account

My old Android phone has completely failed, so I can no longer access Microsoft Authenticator on that device.

I had previously enabled Cloud Backup in Microsoft Authenticator, and I am certain that I am signing in with the same Microsoft personal account that was originally used as the recovery account.

On my new Android phone, I reinstalled Microsoft Authenticator and selected “Restore from backup / Begin recovery” before adding any accounts. I then signed in with the same Microsoft personal account.

However, Authenticator says that the backup is not stored under this account and asks me to try another personal Microsoft account.

I am certain that this is the correct recovery account.

Both the old phone and the new phone are Android devices, so this is not a cross-platform restore issue.

I would like to know:

1. Could this be a problem with the association between the cloud backup and the recovery account?
2. Is there any way for the Microsoft Authenticator team to verify whether a backup still exists?
3. Is there any supported way to recover the original backup instead of manually resetting and re-enrolling every third-party 2FA account?

My old device is completely inaccessible, so I cannot open Authenticator there or create a new backup.

Any guidance from the Microsoft Authenticator or Identity team would be appreciated.