Проблема сообщения между Exchange и Outlook⁠⁠

Так а по каким почтовым протоколам клиенты с почтовым сервером общаются? POP3/SMTP? TLS, IMAP? Проверьте для начала с каждого клиента ping по адресу и по прописанному у клиента имени хоста почтового сервера. Затем посмотрите в настройках клиента протоколы-порты и с каждого же клиента попробуйте telnet имя_сервера порт_сервера

Например, у меня работает соединение наружу командой telnet smtp.yandex.ru 465

То есть у почтового сервера должны быть доступные все используемые почтой на соединение, более того, так как протоколы POP3/SMTP не шифрованные, а обычный текст, то после соединения на их порты, прямо из telnet-клиента можно проверить почту или инициировать отправку письма - это лучший способ проверки доступности чуть ли не из командной строки.

Если в современных виндах Win8/10/11 не имеете telnet-клиента и не знаете как поставить, то возьмите как замену тот же putty.exe.

Специально проверил сейчас на глобальные почтовики – прямо из командной строки из telnet подключается (и у вас должно подключаться) как на простые порты, так и на шифрованные TLS - по крайней мере доступность портов уже проверена.

Если у вас не проходит соединение, то смотрите какие у клиентских машин настройки Firewall'а / Защитника / всяких антивирусов с фильтрующими приблудами – DrWeb Mail Security Suite / KAV и прочие AVAST'ы – наверняка либо Защитник винды не пропускает сетевые соединения с клиента/с сервера, либо на рабочих станциях антивирусы поставили и сроду не настраивали, а у некоторых ещё и по 2-3 штуки одновременно стоят и вообще ничему не дают работать.

Ну и если даже пинги не ходят, то смотрите правильность маски подсети и чтобы протокол ICMP тоже не блокировался в Firewall'е – иногда из-за спешки-опечаток или настройки по DHCP даже в локалке маску ставят не 255.255.255.0, а что-то пожёстче, что сокращает диапазон адресов в сети и чисто логически пакеты не проходят, особенно если IP-адрес сервера с края диапазона, отрезаемого маской подсети.