1. Написать текст ошибки которая возникает в Outlook
2. Посмотреть логи Exchange
3. Не работает у всех или только у некоторых?
4. Если только у одного или у нескольких, значить проблема с ихними компами.
Сделай диагностику:
1. Ping до майл сервера по имени хоста и IP
2. Телнет 110 и 25 порт если конечно не TLS/SSL соединение
3. nslookup'ом разрешение имени почтового сервера, прямое и обратное
4. Встроенный фаервол или антивиря проверь у машин, может он мешает.