"Authenticator does not restore backup. It is not possible to recover."

Question

When trying to restore my Authenticator backup on the Android app, it says there's no backup associated with my account (even though there is — I've successfully restored it once before).

Recovery is not possible. Your backup is not stored in... Try signing in with a different personal Microsoft account.

But I don’t have another personal Microsoft account.

I’ve already cleared the app data, cleared the cache, uninstalled and reinstalled the app, and made sure to tap on "Backup" before adding any accounts (again, I’ve restored this same backup before), but nothing has worked.

Has anyone else experienced this and managed to fix it?