akelsey

В файле main.cf корректно установить как минимум mynetworks:
mynetworks = 192.168.0.0/24 (добавить сабнет разрешенный для отправки)
что позволит рилеить почту с вашей подсети через ваш постфикс.
причем тут днс - не понятно.

Если я правильно понял схему:
Postfix - санитар, Exchange - корп. почтовик.
В Exchange вы можете завести такое кол-во Accepted Domains пока позволяют ресурсы. Но у одного пользователя может быть только один PrimarySMTPAddress. И отправлять от имени другого домена проблематично.
Есть кривая схема каждому юзеру в первом домене - завести шаренный ящик с его именем, с каким-то префиксом, дать этому ящику PrimarySMTPAddress второго домена, и отправлять почту от этого шаренного ящика. Да не удобно, но без 3rd party app (о которых я не знаю даже есть ли они) - сделать это невозможно.
Либо написать свой addon для Outlook - где юзер будет выбирать имя домена с которого отправлять (он будет писать что-то в хидер), а для Exchange написать транспортный агент, который будет вылавливать этот хидер и отправлять почту с нужного домена - меняя хидеры Envelop.

Как я понял на Exchange в качестве смарт-хоста указан постфикс.
Первое что нужно сделать это проверить телнетом с сервера Exchange доступ на 25ый порт Postfix. Если он недоступен, то Expiration закономерен, Exchange пытается отправить письма на несуществующий хост.

Возможно сервер слушает подключение на 127.0.0.1, посмотрите вывод:
netstat -na | grep :25
должно быть
0.0.0.0:25
или
xxx.xxx.xxx.xxx:25
если же
127.0.0.X:25 - то надо сервис смотреть.

X-MS-Exchange-Organization-SCL: 6 = метка уровня вероятности нежелательной почты
X-MS-Exchange-Organization-PCL: 2 = метка уровня вероятности фишинга

6 - это очень большое значение, кто-то ставит вам эти заголовки. По всей видимости EOP.

vim virtual
nonexistedmailbox@mydomain.ru existedmailbox@mydomain.ru
:wq

postmap virtual
service postfix reload

почта с несуществующего ящика будет приходить на указанный...

1. Ставим Exchange, настраиваем send/recieve connectors, прописываем accepted domains, прописываем recipient policy
2. Верно, релеем всю зону company.com -> Exchange IP (не забываем открывать smtp)
3. Миграцию почты я б оставил на потом, т.к. почта юзеров останется в их старом зандербёрде - они её смогут так же получать через что-та у вас стоит (Dovecot?)
4. Я бы оставил постфикс, или бы настроил его на отдельном VPS/VDS как смартхост для эксчендж и как антиспам+антивирь, и после проверки релеить почту на Exchange
5. Сделать третий шаг, уже не спеша - когда почта ходит и уходит с Exchange.