Wenn derselbe Exchange-Account gleichzeitig auf iPhone und iPad betroffen ist und das definitiv richtige Passwort auf beiden Geräten als falsch abgelehnt wird, würde ich den Account zunächst nicht löschen. Das spricht eher dafür, dass die Anmeldung am Exchange-Server bzw. die Authentifizierung scheitert.
Als ersten Test würde ich mich mit denselben Zugangsdaten über das Webmail deiner Firma anmelden. Funktioniert das, sind Benutzername und Passwort grundsätzlich in Ordnung.
Danach wäre bei einem Firmenaccount der Administrator bzw. die IT der sinnvollste Ansprechpartner. Dort sollte geprüft werden, ob für deinen Account beispielsweise Exchange ActiveSync, die moderne Authentifizierung oder eine Zugriffsrichtlinie betroffen ist. Auch eine abgelehnte Anmeldung kann sich auf dem iPhone lediglich als „Passwort falsch“ zeigen.
Gerade weil es auf zwei Geräten gleichzeitig passiert, wäre interessant, ob die IT in den Anmeldeprotokollen zum Zeitpunkt des Fehlers eine Ablehnung sieht. Damit lässt sich meist deutlich besser feststellen, warum Mail die erneute Anmeldung verlangt, als durch wiederholtes Löschen und Neueinrichten des Accounts.
Apple selbst empfiehlt bei solchen Passwortabfragen ebenfalls, zunächst den Zugriff beim Mail-Anbieter zu prüfen und bei Firmenaccounts Sicherheitsfunktionen und Einschränkungen mit dem Systemadministrator abzuklären. Das Löschen und erneute Hinzufügen des Accounts ist dort erst ein späterer Schritt.
Ich würde daher erst neu einrichten, wenn die serverseitige Prüfung nichts ergibt. Wenn das Problem nach Updates schon mehrfach aufgetreten ist, wäre die eigentliche Frage für eure IT, warum die vorhandene Exchange-Authentifizierung anschließend nicht mehr akzeptiert wird.
Zum Nachlesen: Apple Support, Artikel „Empfangen von E-Mails auf deinem iPhone oder iPad nicht möglich“, Artikelnummer 102578.