If you have an internal Exchange server powered on, and you have migrated to Office 365, you might see some Outlook clients (2016/365) having issues.
To try to fix the issue and force the connection to Office 365 instead of the internal server, you can try adding this registry key:
Path: HKEY_CURRENT_USER\Software\Microsoft\Office\14.0\Outlook\AutoDiscover
Value: ExcludeScpLookup
Type: DWORD
Data: 1
This way, the domain-joined clients will not be able to ask Active Directory an SCP entry and directly query the AutoDiscover (which should be fine, if you migrated to Office 365, as it’s one of the requirements).