Why am I not receiving any MFA challenges for my Microsoft account, and getting an "Error checking for notifications" when pulling down to refresh? (Android)

Question

For at least a couple of days (since 2024-04-22), I haven't been receiving any MFA challenges in the Android Microsoft Authenticator app for my Microsoft personal account. I've had ones come through for a Work account set up in there. Steps to reproduce:

1. Open an In Private tab on Edge, and go to https://account.microsoft.com
2. Click the "Sign in" button and enter my Microsoft personal account email address and click "Sign in"
3. On the next page, enter the password and click "Sign in"
4. On the next page, "Verify your identity", I choose "Approve a request using my Microsoft app"
5. The next page that appears asks me to "Approve sign-in request" and "Open the Microsoft app (such as Authenticator or Outlook) you use for approving sign-in requests and approve request ABCXYZ". However, no notification appears on my phone. With the Authenticator app open, no popup appears (as it previously would have done). If I pull down to refresh, I get the message "Error checking for notifications" with an "OK" button.
6. If at "Verify your identity" I choose to enter a code from my Microsoft Authenticator app, then enter the revolving code that is valid for 30s, I get the message "Too many invalid codes have been entered. Please try again later"
7. If at "Verify your identity" I choose to send a code to my backup email address, this works fine and I can successfully sign in.

Things I have checked:

• The Microsoft Authenticator app on my Android has notifications enabled and is exempt from battery optimization.
• I have the app installed on two Android devices, both backing-up/restoring from the same Microsoft personal account I'm having issues with. I get the same behaviour on both devices.
• The Microsoft Authenticator app is up to date
• I have looked at the security activity on my account and I can see many attempts by people overseas to access my account, all of them unsuccessful due to incorrect password.

What could be the problem here? How can this be fixed?