If some of your Office 365 users are receiving an error 456 when trying to connect to Exchange autodiscover, then multifactor authentication could be the culprit!
To see if your users are experiencing this issue, have them go to https://testconnectivity.microsoft.com and run the “Outlook Autodiscover” test using their own credentials. If the result is a failure, save the whole results to HTML and do a search for “456” in the saved HTML document.
Specifically, you are looking for this error: –
An HTTP 456 Unauthorized response was received from the remote Unknown server. This indicates that the user may not have logged on for the first time, or the account may be locked. To logon, go to http://portal.microsoftonline.com.
This could mean that you have multifactor authentication “enforced” at the account level, rather than via specific scenarios such as those available for Conditional Access. As autodiscover does not know how to handle multifactor authentication, and the account itself has multifactor authentication enforced, the service is unable to be used by the affected account.
The resolution is to disable the user for multifactor authentication and then have them re-setup and use conditional access rules to require multifactor authentication instead for the required services.