Hi, we were facing the same issue in our company. It started just after enrolling all our computers into Microsoft Intune. For more than a year we tried a lot of things without success. Recently we discovered that it was our own proxy that was creating the issue. Its a proxy on a Sophos UTM. Something about it seems to not communicate correctly with the Azure user authentication or the application security checks...We have the proxy configured through a WPAD file. We tried changing some settings but only disabling the proxy on the affected computers fixed the issue. In a couple of months we will update our vpn/proxy to Zscaler and hope that it doesnt happen again.
I post this here hoping to help other people in the same situation so that they don't have to spend months investigating as we have done in our IT department.
Cheers.