After a long conversation with Microsoft, the end result was somehow federation between Microsoft and our ADFS servers was severed. Here is how we fixed it.
Remote desktop to your ADFS server (not the proxy)
Open the Windows Azure Active Directory Module for Windows PowerShell as an administrator If you are old to ADFS, this was formerly called Microsoft Online Services Module
Execute the following command: Connect-MsolService Type in your Office 365 admin credentials. I highly recommend you use a cloud based user called firstname.lastname@example.org in the case you cannot federate.
Execute the following command: Update-MsolFederatedDomain Type in the domain name you federate to office 365 (yourcompany.com). Successfully updated ‘yourdomain.com’ domain. message when done.
Execute the following command: convert-msoldomaintostandard -domainname mydomain.com -passwordfile pass.txt -skipuserconversion $true This command will break federation (essentially turn it off) to Office 365. This will not lose your mailboxes, settings, etc.
Execute the following command: Convert-MsolDomainToFederated This command will re-establish federation to Office 365
Execute the following command: Update-MsolFederatedDomain This command will update URLs or certificate information within AD FS and Office 365. Note: If you have multiple domain names being federated, please use the following command: Update-MSOLFederatedDomain -DomainName mydomain.com -supportmultipledomain
Next, I restarted my proxy server, reran the ADFS wizard to ensure the proxy could communicate to the primary ADFS server, and waited a minute or so.
At this point, authentication began to work properly again.
Quelle: Office 365 – Can’t sign in – Error 80041317 | Jack Stromberg