Using Outlook for iOS for personal email and calendar management
I was experiencing this same issue while trying to create a new corporate MDM iOS profile for Outlook.office365.com. After opening a ticket with Microsoft, we were able to find a solution to this issue within our environment. Initially the support engineer thought the issue was related to MFA being enabled or a conditional access policy being in place within Azure. After we ruled those two possibilities out, we were asked to confirm that Exchange Active Sync was enabled for my user. As it turns out, that was not enabled for me but it seems it was enabled for nearly all other users.
I'm not sure if this advice will be of much help to anyone else but it absolutely fixed the issue for me. If not, it might be worth checking MFA policies and conditional access policies for your azure/office 365 tenant. Hopefully this information will help someone.