akelsey

купить впску (лучше две) по доллару за месяц, настроить там postfix/exim/sendmail по вкусу и эксчи натравить на смарт-хост
PS
Либо попросить провайдера открыть рилей с их почтового сервера.

Не очень ясна задача, ничто не мешает сделать цепочку postfix - edge - exchange
Просто обычно для эджей создается подписка, который стоит в дмз, на нем поднят адам, этой подпиской создаются два коннектора, один для исходящей почты во вне, второй соединитель на эксченджи которые стоят в вашей сети.
Т.е. по умолчанию всю почту эксченджи роутят на эджи, которые уже роутят почту во вне, но на определенный домен - вы можете их роутить так как вам угодно.
Что почитать? Всё )
Начните отсюда: https://technet.microsoft.com/library/bb124558(v=exchg.141)

В Microsoft Exchange 2013 есть и гибкие "Transport Rules" и "DLP".
Нужный функционал, они вам обеспечат.

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