In January I changed my email address but kept same domain and mail server. At same time, I set old account up as an Imap account with same password as before. Everything worked fine. Then last week I deleted the old Imap email account, and I started having problems with the new account being unable to connect to the mail server. This happened on IOS mail on iPhone X, and on Outlook 2016 running on a desktop. I was able to rectify desktop only by completely wiping and setting up again (clearing windows credentials didn't work). On the iPhone I have cleared keychain, deleted account and set up again, wiped phone and set up again as a new phone but still connected to my apple id (& therefore icloud) and still the exchange is failing to log in.
What I am seeing is that somewhere it has saved the log in for the mail server, and it is still using the old log in, hence why it worked for 3 months, as the old username was still valid until I deleted it last week.
The new exchange account is set up with correct username, but it is getting this old username from somewhere and using it for log in. I can see in Settings>Accounts & Passwords that the old username is there, and when I delete it, the username re-appears later. It seems the push still works, as I do get mail coming through occasionally, but when I try to send or manually update initiating it from the iPhone, it fails log on.
There must be somewhere the IOS has saved the log in for the mail sever, and storing it in icloud, so that it is bringing it back in a restore situation.