А сам Windows 2008 R2 может отказываетса принимать запросы с сети 192.168.9.0/24. На самом почтовике какойто фаервол настрое или антивирус. Например у меня был eset smart security так он запросы с другой сети не принимал, пока не было допиляно его фаервол внутрений.

Почта ходит через ISA сервер (На нём разрешения прописаны)

Что то я нипонял ничего. А у вас почтовик на какой ОС настроен. Может фаервол на нём что то режет?

Почтовик на Windows 2008 R2

Ну тогда нужно разбиратса из настройками фаерволов на етих 2 шлюзах. Они скорей всего настроены так что пропускают тока то что надо, а почта в это "надо" не входит.
Так что для начала показывайте настройки iptables со шлюзов.

на 9.1

# Generated by iptables-save v1.4.7 on Mon Apr  1 12:15:48 2013
*nat
:PREROUTING ACCEPT [19:6541]
:POSTROUTING ACCEPT [17:6293]
:OUTPUT ACCEPT [1:108]
-A PREROUTING -s 192.168.9.0/24 -i eth0 -p tcp -m tcp --dport 80 -j DNAT --to-destination 192.168.7.1:3128
-A PREROUTING -s 192.168.9.0/24 -i eth0 -p tcp -m tcp --dport 443 -j DNAT --to-destination 192.168.7.1:3128
COMMIT
# Completed on Mon Apr  1 12:15:48 2013
# Generated by iptables-save v1.4.7 on Mon Apr  1 12:15:48 2013
*filter
:INPUT ACCEPT [146:62239]
:FORWARD ACCEPT [287:227925]
:OUTPUT ACCEPT [174:186744]
-A INPUT -p tcp -m tcp --dport 25 -j ACCEPT
COMMIT
# Completed on Mon Apr  1 12:15:48 2013

на 7.1

# Generated by iptables-save v1.4.7 on Mon Apr  1 12:26:57 2013
*filter
:INPUT ACCEPT [11790:10426609]
:FORWARD ACCEPT [17223:12101893]
:OUTPUT ACCEPT [9753:3015256]
-A INPUT -p tcp -m tcp --dport 25 -j ACCEPT
COMMIT
# Completed on Mon Apr  1 12:26:57 2013

Из сети 192.168.9.0/24 есть доступ к mail-серверу по нужным портам (smtp, iamp, etc)?

Пинги есть.
Telnet не подключает

# Generated by iptables-save v1.4.7 on Mon Apr  1 10:59:38 2013
*filter
:INPUT ACCEPT [8448159:2989602794]
:FORWARD ACCEPT [17069416:10935058003]
:OUTPUT ACCEPT [9468050:9173814173]
-A INPUT -p tcp -m tcp --dport 25 -j ACCEPT
COMMIT
# Completed on Mon Apr  1 10:59:38 2013
# Generated by iptables-save v1.4.7 on Mon Apr  1 10:59:38 2013
*nat
:PREROUTING ACCEPT [721025:70433780]
:POSTROUTING ACCEPT [326687:20845693]
:OUTPUT ACCEPT [11364:765287]
-A PREROUTING -s 192.168.9.0/24 -i eth0 -p tcp -m tcp --dport 80 -j DNAT --to-destination 192.168.7.1:3128
-A PREROUTING -s 192.168.9.0/24 -i eth0 -p tcp -m tcp --dport 443 -j DNAT --to-destination 192.168.7.1:3128
-A PREROUTING -s 192.168.9.0/24 -i eth0 -p tcp -m tcp --dport 25 -j DNAT --to-destination 192.168.7.1:3128
-A PREROUTING -s 192.168.9.0/24 -i eth0 -p tcp -m tcp --dport 110 -j DNAT --to-destination 192.168.7.1:3128
COMMIT