Эта ошибка связана с тем, что после переноса почтового ящика пользователя с сервера MS Exchange на другой сервер, в частности в облако Office 365, изменился адрес сервера, про что аутлук не догадывается и пытается отправлять письма на старый сервер.
Для того, чтоб исправить проблему, создайте сообщение, начните вводить адресата и после того как будет предложен адресат, отправка на которого вызывает ошибку, удалите его нажав крестик.
Также можно удалить из списка все почтовые адреса, что и рекомендуется сделать, так как возможно в списке адресов имеются еще проблемные пункты. Сделать это можно открыв меню Файл — Параметры
В открывшемся окне выбрать Почта и прокрутив вниз найти кнопку Очистить список автозавершения.
После удаления контактов из списка автозавершения придется один раз контакт вбить руками, после чего он снова будет выводиться из кэша.