This is specifically an issue with corporate M365 accounts when a user tries to migrate to a new phone without access to the old phone where the authenticator was setup.

Personal MS accounts can backup their auth secret keys to cloud storage, and when signing in on a new device, it authenticates you with your cloud storage (Google/Apple) and properly restores your MS Authenticator app.

The issue is that while MS says you can backup your corporate M365 accounts in MS Authenticator, it doesnt actually store the secret key, so it’s useless.

Have your administrator enable TAP (Temporary Access Passwords) on the tenant. Then an M365 admin can create a TAP for your account that lets you login without a password/2FA. You can use the TAP to login and rejoin MS Authenticator app. The TAP expires in 1 hour by default.