Круто! А логи будут какие-нибудь? Детальное описание, что и как отваливается, выхлоп tcpdump, traceroute....
Судя по тому, что вы написали можно построить миллион предположений, как именно у вас "отваливается NAT":
1. Администратор у провайдера вас недолюбливает. Поэтому пока вы все настраиваете, издевается над вами. Через случайное время с момента поднятия линка запрещает траффик в сторону почтового сервера. Вы пишете сюда, а он над вами смеется.
2. ....