Trying to reset up the email account of a domain that’s been defederated from one 365 tenant to another , and for some reason, Outlook on the iPhone had cached the old server

“The account needs to be added as an external user to the tenant first”

Deleting the Outlook Mobile App and redownloading it fixed the issue

Clearing the App Cache might work as well if you can!