Had this issue again which caused major headaches. Stemmed from the fact that the user had previously set up a Microsoft account using their business email address. After setting up Office365 for them they could not authenticate. Got them to change their email address associated with the old MS account. Removed any cached Credentials in Windows 10. Signed out of all Office Apps and OneDrive.
Switched off the Microsoft Security policies in Azure AD as the MFA was a pain. Every time I added their account to Outlook 2016 it would link to the old on premise Exchange server.
I followed the procedure given here
and bizarrely this fixed the issue.
Basically add the Office365 account to Windows Mail where you specifically select Office365. Once connected close Windows Mail and proceed to add the account via Outlook or a new profile via Control Panel to add O365 to Outlook 2016.