Я вижу тут несколько вариантов:
1. Если я правильно понял, то проблема только с астериском, т.е. остальные приложения отправляют пакеты нормально? Возможно проблема именно в астериске (там есть тонкие моменты в процедуре отправки инвайта в котором указывается внешний ip адрес), а что говорит tcpdump есть там что то интересное?
2. Если прописывать только одно правило SNAT при изменении дефолтного шлюза, вы сможете увидеть действительно отправляемые пакеты попадают не в то правило SNAT.
Проблема очень интересная, если будет желание напишите мне в ПМ или на jabber постараюсь помочь.
