На свежеустановленном Exchange Server 2013 сообщения отправлялись, но никуда не приходили. Если открыть Exchange Toolbox, то в очередях сообщений все отправленные висели с ошибкой “451 4.4.0 dns query failed”.
Решение
Проверяем свойства подключения Exchange:
Get-NetworkConnectionInfo
Копируем AdapterGUID:

Теперь посмотрим что об этот думает Exchange (вводим на на транспортном сервере, который занимается отправкой почты):
Get-TransportServer -Identity exch-hub-01 | fl *DNS*
Получаем:

Явно что то не то.
Правим командами (жирное заменить на свое):
Set-TransportServer –Identity exch-hub-01 –InternalDNSAdapterGUID 2ad981fb-388b-4aef-815b-61eccec543b7
Set-TransportServer –Identity exch-hub-01 -ExternalDNSAdapterGUID 2ad981fb-388b-4aef-815b-61eccec543b7
Еще раз проверяем:
Get-TransportServer -Identity exch-hub-01 | fl *DNS*
Через несколько минут очередь отправки начнет уменьшаться. Или, можно подтолкнуть правой кнопкой мыши.