При настройке Exchange в одной компании встретил такую же ошибку о недоступности почтового сервера и файлов OST.
Используется следующая конфигурация сервера:
Windows Server 2012 R2 с установленной ролью AD DS и Exchange 2013 SP1.
на сервере два сетевых интерфейса: внешний и внутренний.
Клиенты не используют DNS от AD на своих компьютерах, по этому подключаются к почтовому серверу через его внешний адрес.
Сами клиенты выходят в интернет с другим адресом из той же сети, что и внешняя карта сервера. По этой причине сервер считает этих клиентов
внутренними!
При подключении Outlook 2010\2013 появлялась следующая ошибка:

на первом скрине, Outlook не мог найти пользователя на сервере. на втором скрине пишем
внешний адрес сервера - serv6.domain.ru
но после проверки Outlook-ку подставлялся
внутренний адрес serv6.exchange.domain.ru потому, что см. описание выше. Но этого адреса во внешнем ДНС не было (там же где и autodiscover пишется).
По этому Outlook не мог найти сервер. Ситуация решается двумя способами:
- правка ссылок в Exchange для клиентов на правильное имя, которое есть во внешнем ДНС
- добавление во внешний ДНС записи о сервере для внутренних клиентов, т.е. для всех.
мы выбрали второй, так как это гораздо проще
