I actually have the same issue.
A couple of more things that maybe shed light on what might be happening:
I use Office 365 on my laptop and on my iPad, both of which have issues generating Authenticator notifications from my FP4.
- It starting happening after the latest OS update (end of August I believe), before that I did not have any issues
- I have now re-installed the MS Authenticator app several times
- When setting up the 2FA using MS Authenticator for the first time, the first request for authentication (to confirm the app is generating responses) does come through, resulting in a successful setup of the App.
- Any subsequent notifications however do not manage to get to the phone/App from my laptop
- The codes generated by the Authenticator app also do not get accepted as 2FA responses (which should normally work as this is the fallback when the phone is offline)
- Interestingly enough, when I access the office 365 environment through the browser on my phone, the notifications do make it through to the App. Which seems to suggest there is something off between the FP4 and the other devices.
- My phone takes the network time, less then 1 sec time difference between the phone and other devices.