Alexey Dmitriev

Этот механизм называется mail autodiscover.
Это специальные DNS записи плюс специальные страницы на вебсервере.

P.S. В гугле куча ссылок по запросу "автоопределение почтового сервера".

Покупать один сертификат со всеми нужными доменами в SAN

Никак. Только подключать второй аккаунт с по другим протоколам.

Нигде.

Значит DNS записи прописаны некорректно или соответствующие xml файлы отсутствуют\недоступны.
Как раз autoconfig И autodiscover - это те записи в DNS, которые определяют автоматический поиск почтовых серверов и настройку почтовых клиентов. Ну и соответственно соответствующие xml файлы должны быть доступны по этим DNS записям

1. Купить дешевый VPS, настроить почтовый сервер.
2. Перенести почту на сервис почты для домена почты яндекс или почты mail.ru и т.п.

Используя Punycode домена

Никакой конкретики по версиям, никаких попыток сделать самому и описать, что делали и что не получилось.
GAL это объект в AD в Configuration Naming Context, и у него стандартный менеджмент ACL во вкладке Security, как у любого объекта.

Настройте SPF, DKIM, DMARC, PTR.
Проверьте домен на postmasterе почтового сервера, куда отправляете почту. Можно начать с postmaster.mail.ru

1. Проброс портов (DNAT).
2. Load balancer типа Haproxy.
3. Сервер клиентского доступа (Client Access role) Exchange

Предполагаю, что если вы спрашиваете о таких банальных вещах - знаний у вас не хватает и я бы вам не советовал выпускать exchange наружу любым из способов, если вы и ваша компания не хотите нарываться на проблемы типа https://www.microsoft.com/security/blog/2021/03/02...

Нужно настроить почтовый сервер postfix\sendmail\exim с DKIM, который будет слушать на localhost и сможет отправлять письма. Функция аналогична команде mail на сервере.