Authenticator won't add account due to "notification" settings

Question

I have recently reset my Android Samsung Galaxy S10 to factory. Installed all updates and installed the latest version of Authenticator.

When attempting to add my Microsoft Azure/M365 account to the app, I receive the below error.

I have turned off battery optimization for this app and confirmed that it has both normal push notification permissions and Do-Not-Disturb permissions.

Regardless, I can not add the account. Additionally, our M365/Azure admins have validated that I am not a blocked user in the Azure MultiFactor Authentication blade > Block/Unblock Users.

Error Message:

Unable to add the account
We couldn't add the account. Please verify that the activation code is correct and push notifications are enabled on your device for this app.

Steps to Replicate:
Install Microsoft Authenticator on Android 10.
Add account using the Scan QR code option.
Receive the above error.

Other troubleshooting steps:
Removed all other forms of MFA from account, attempt to add only Authenticator, no luck.
Attempted over wifi and mobile data, no luck.
Tried manually typing both the Code and URL, no luck.
Tried all available docs/help articles. None seem to identify this specific issue or provide a fix.

Answer 1

Man, this has been a battle, but I think I can help you both. We have been battling this from a Verizon MDM direction, but it ended up just being a phone setting. I noticed in the authenticator app settings Uninstall and Force Stop were greyed out, and I couldn't even do it from Safe Mode. What ended up fixing it was Settings -> Security and privacy -> Other security settings -> Device admin apps -> Unselect Authenticator.

As soon as I did that I could go into the App and turn on notifications, and they actually stayed on. Maybe it won't help you all, but I spend probably four hours working on this and figured I would at least toss it out there for you. My MDM manager did put me in the admin group before I made this change, but I'm not sure that was required or not. If you aren't able to turn this off then maybe get them to temporarily do the same for you. Hope it helps!