iCloud has nothing to do with this problem. It is a BT server problem which has been going on for some time and the best advice when it happens is to do nothing, especially do not change passwords or delete the account from your phone as that can cause more problems than it solves.
The first thing to do when it happens is check to see if you can log on to your email account via a web browser. If you can there is obviously nothing wrong with your password or account hence the advice to do nothing.
If the problem did not resolve its self after a day or two or in your instance where you have deleted the email account from your device you should stop your iPhone and any other devices from checking for email.
Once you have done that, change your email password and check that you can access your email via webmail (on a browser).
If that works you should wait at least 30 minutes to an hour and then add the new password to your iPhone and again check it works. If it does then move onto the next device if you have one.
If the above does not resolve the problem, when you change your BT password on an iPhone/iPad/Apple device it may only change for INCOMING mail.
To change the outgoing mail password you have to go into Settings; then scroll down to Mail, Contacts, Calendars. From there select the BT email account and select the account where it is listed under IMAP.
You will find the details for the account and can change the password for the Incoming server there, the outgoing mail server only shows SMTP and mail.btinternet.com You have to tap on that Primary Server in order to find where the Outgoing password is hidden so you can update it.
When setting up the email account on your device you are best to set it up manually, using "other" and ensure that you are using the correct settings as per this link.
https://www.bt.com/help/email/manage-email-account/manual-settings/what-are-the-settings-for-outgoin...
