Es gibt einige Lösungsansätze:

Zum einen können Sie sich über die OWA an dem Postfach anmelden und die Nachricht von dort aus versenden. Dieser Weg funktioniert immer.
Wenn Sie auf das Versenden aus Outlook bestehen, dann müssen Sie vorher ein paar Schritte mehr vornehmen und es gibt keine Garantie, dass Outlook sich damit zum sofortigen erfolgreichen Versand überreden lassen kann. Sie müssen zuerst entweder im Reiter Datei über Kontoeinstellungen das Adressbuch herunterladen.

Alternativ können Sie auch über dem Reiter Senden/Empfangen im folgendem Bereich Senden-Empfangen-Gruppen das Adressbuch herunterladen.

Im nächsten Schritt erstellen Sie eine neue Nachricht und wählen das Von-Feld aus. Gehen Sie auf das X hinter der Adresse, mit welcher der Versand bereits fehlgeschlagen ist, und entfernen diese. Nachdem Sie die Nachricht verworfen haben, erstellen Sie eine neue Nachricht und gehen erneut auf das Von-Feld und wählen die Absenderadresse aus dem Adressbuch. Falls die Adresse nicht sichtbar ist, bedeutet dies, dass das Adressbuch nicht aktualisiert wurde und sehr wahrscheinlich der erneute Versand wieder fehlschlagen wird. Wenn die Adresse sichtbar ist, dann können Sie die Nachricht wie gewohnt versenden.

Der nächste Versuch wäre, Outlook in den Online-Modus zu versetzen. Dieser Modus ist auf eine permanente stabile Internet-Verbindung angewiesen und verursacht sowohl mehr Last auf Ihrer als auch auf Server-Seite, wodurch im dauerhaften Betrieb im Online-Modus Outlook manchmal träge erscheinen kann. Die Voreinstellung in Outlook ist der Cache-Modus und wir empfehlen nicht den dauerhaften Betrieb in Online-Modus.
Um auf Online-Modus umzuschalten, müssen Sie in Outlook im Reiter Datei die Kontoeinstellungen und wieder Kontoeinstellungen auswählen.

Im nächsten Fenster müssen Sie auf dem Reiter E-Mail, das entsprechende Konto mit Ändern auswählen.

Hier müssen Sie das Häkchen bei Exchange-Cache-Modus verwenden entfernen und anschließend alle Dialoge mit Weiter bestätigen und Outlook neu starten. Im Online Modus wird das Adressbuch ebenfalls direkt ohne Zwischenspeicherung verwendet. Nach dem Versand empfehlen wir das Zurückschalten auf den Cache-Modus.

Ein neues Outlook Profil ist nicht immer die Mittel der Wahl. Dabei ist es wichtig das alte Profil nicht zu löschen, sondern vorerst ein zusätzliches Profil anzulegen. Man sollte im Blick behalten wie groß das eigene Postfach ist. Das Herunterladen von mehrere GB Daten ist nicht immer das was man sich antun will oder leisten kann.

Falls Sie Outlook for Mac verwenden, dann müssen Sie mit der OWA arbeiten. Im Outlook for Mac wird das Adressbuch alle 24 Stunden automatisch aktualisiert und eine manuelle Aktualisierung ist laut Microsoft nicht vorgesehen.