I've got a client whose Office 365 I federated with Okta. SAML works if clicking one of the Office app shortcuts from the dashboard. However if you go to portal.office.com and attempt to sign in with validuser@clientdomain.com then it does not send you to Okta but instead acts like there is no federation and prompts you to sign in to O365 normally. If you type INValidUser@clientdomain.com then it always redirects to Okta properly. This is not universally true though. Some valid usernames do get redirected to Okta but not many. We have not tested them all but somewhere around 30% maybe get properly redirected whereas the rest do not get redirected. Authentication is functioning fine whether they login to O365 or Okta. The client syncs users to Okta with the AD sync client and the O365 users are synced between onprem and Azure via Azure ADConnect. I have checked the ImmutableIDs and they are correct and present in Okta Office 365 assignments. I have tried clearing refresh tokens as well. I've been comparing all kinds of attribs and things between the working and non-working users and cannot find a solid correlating factor. We tried turning off all their conditional access policies, etc. but no luck. Looked at fiddler traces and the users which do not redirect properly don't show any traffic towards Okta at all. MS just refuses to recognize that these users are federated but their UPN and primary email are the federated domains. I'm running out of ideas and MS support is well... what you'd expect from Office 365 level 1 support on the weekend. Basically not even trying.