Authenticator not sending notification when signin in Authenticator

Question

My phone have been stolen, I had work account logged in there.

Now I have new phone and after installing I am trying to log in and it requests approval of a notification that never arrives, I also cannot log in on any other app like Teams, Outlook, etc because it requires as well approval of notification from Authenticator, that doesn't pop up either. I have make sure that the battery optimization and all sort of notification permissions are allowed. Reinstalling doesn't work either.

I have already spoke to help-desk of my company and they disabled the two-factor for one day but the problem remains.

Answer 1

You can restore from backup (assuming there was one) but make sure no accounts have been added to the newly install app. Then sign on with recovery account to do the restore.

You can recover your account credentials from your cloud account, but you must first make sure that the account you're recovering doesn't exist in the Microsoft Authenticator app. For example, if you're recovering your personal Microsoft account, you must make sure you don't have a personal Microsoft account already set up in the authenticator app. This check is important so we can be sure we're not overwriting or erasing an existing account by mistake.
https://support.microsoft.com/en-us/account-billing/back-up-and-recover-account-credentials-in-the-authenticator-app-bb939936-7a8d-4e88-bc43-49bc1a700a40

--please don't forget to upvote and Accept as answer if the reply is helpful--