В общем, никто мне не ответил, думаю, ввиду неконкретности вопросов.

В результате, сделал всё сам...
Вкратце опишу что сделал, мало ли, кому будет интересно.
Эксченджевый сервер задвинул за шлюз.
Разрешил ip_forward: echo "1" > /proc/sys/net/ipv4/ip_forward
Первым делом, разрешил вход по ssh, чтобы можно было в удовольствие посидеть дома всю ночь и поковыряться с правилами iptables.

iptables сконфигурил для начала через guarddog (руками пока не удалось, в ближайшее время переделаю стопудово, ибо файл, который получается после выгрузки правил, которые генерит guarddog, не шибко читабелен), вручную добавив правила для проброса пакетов на SMTP, HTTPS и RDP во внутреннюю сетку по следующему принципу:
iptables -t nat -A PREROUTING -p tcp -d ext_gate_iface_ip --dport 3389 -j DNAT --to-destination rdp_server_ip:3389
iptables -t nat -A POSTROUTING -p tcp --dst rdp_server_ip --dport 3389 -j SNAT --to-source int_gate_iface_ip
Где:
ext_gate_iface_ip - внешний IP шлюза, на который приходят соединения.
int_gate_iface_ip - внутренний IP шлюза.
rdp_server_ip - IP сервера, на который пробрасываем соединение (в данном случае это RDP).
В результате, Exchange за милую душу принимает и отправляет почту для домена, поддержка которого прописана в bind на шлюзе, как я и хотел.
На шлюзе поднял bind9, в который почти ноль в ноль перенёс настройки с Windowsкого bind, которые поддерживали зону раньше.
Понятно, разрешил вход для DNS запросов из инета. Зона поднялась, всё работает.
Если свою зону держать не нужно, можно вместо бинда поставить пакет dnsmasq. Он практически не требует настройки и работает кэширующим dns сервером.
На шлюзе поднял OpenVPN, с которым чудно работают клиенты под винду.
Делал вот по этой инструкции (смотрите внимательно, там автор дэху с путями напутал, поправил в одном месте путь на /2.0/, а потом забыл это указывать):
http://www.ventanazul.com/webzine/articles/openvpn-ubuntu-and-hulu(Замечание: под вистой столкнулся с тем, что версия клиента openvpn-2.0.9 не может прописать маршрут в таблицу маршрутизации виндов из-за каких-то Windowsких же косяков. Под висту надо ставить вот этот клиент:
http://openvpn.net/release/openvpn-2.1_rc12-install.exe)
Сейчас, однако, настраиваю всё-таки проброс PPTP соединений на внутренний сервер, чтобы юзера могли пока настроенными уже соединениями подключаться.
На клиентах в сети DNS сервер указал внутренний, Windowsкий. Шлюз по умолчанию, понятно, Linuxовый внутренний интерфейс.
Как-то так.
----------------------------------------------------------------------------------------------------------------------------
З.Ы.
Это всё конечно ещё править надо, руками переписывать правила iptables, сквид опять же, учёт трафика всякий. Осознаю.

Но это реально работающая связка, на которую уже можно пересадить народ, и доделывать всё остальное в рабочем порядке. Может кому пригодится..

Отдельное впечатление: Информации в инете реально до-фига!!.. Яндекс и Гугл решают.
Всем удачи!