If you control the receiving end of the calls,like calls from hotels to your gateway or call relay, there is a very easy,simple and not too expensive solution: VPN router.
Get a cheap VPN router, put the VPN router on the customer premise, betwen the I.P. phone and the LAN/internet.
On your gateway, put another VPN router on front of the gateway.
The customer will “tunnel”trought the NAT and even some firewalls, for sure they will go trought the hotels NAT.
The drawback: Use of bandwith will be higher, because the VPN encapsulation and encription .
If yu could find a router that does tunneling without using any encription, that will be perfect, but so far I have not found any.
If you need any help, write to mike3799@yahoo.com
I do not sell the service,just in case.