The solution, as always, can be found on reddit, but not here.
Please, read: "Outlook for iOS and Android - an error occurred during authentication"
https://www.reddit.com/r/Outlook/comments/1bp044h/outlook_for_ios_and_android_an_error_occurred/
So, if you hosting local AD domain like microsoft.local or somthing like that, which is differ from your e-mail domain microsoft.com. In this case, you must retire this discrepancy.
You must ensure that Outlook users have an AD UPN that matches their email exactly.
Just Add Alternative UPN suffix in Active Directory Domain and Trust snap-in.
After that change user logon name and domain suffix in Exchange admin center.
Easter egg from M$. Happy Easter!