On the off chance this helps:
I have a client who has experienced this, and it generated a Microsoft ticket. Our situation is SP Online / O365; using Exchange on-prem, but ADFS in O365, with a "copy" script - new additions to Exchange get replicated in Active Directory.
Besides the limited connectivity with things like email and outlook from this setup, we would occasionally have experiences where a user who had been able to view everything in the Publishing collection (where everything is visible) suddenly couldn't view the Newsfeed, or a Team Site Owner getting access denied to her own sites.
And this would happen intermittently. Usually in a day their permissions would return. Everything was as expected in the SP user / membership grid.
Microsoft's tech advised us "not to rely on the Everyone or Everyone Except External system groups." They are supposed to inherit any new users with an activated O365 license, but according to him, it's a badly kept secret that they are not reliable.
His recommendation? Create an AD group for All SP Users, and populate it with all Active Directory users.
This is what worked for us after LOTS of troubleshooting and MSFT tickets. And, it gives us an accessible back door via O365 Admin to verify / add users to that group as needed. Apparently the script to copy all AD users into the All SP Users group is also intermittent, but that's a tangent.
Good luck.