Symmetric NAT

Hello experts,

Thank you for helping me out in my previous post.

While speaking with a paying customer (rare commodity
these days) it appeared that he uses a big ISP that
supplies him with NAT. The supplied NAT rotate to
symmetric NAT from time to time. 

So, at the times when it become Symmetric NAT we can
only have “half duplex” conversation. I.E – I can
see/hear him but not vice versa.

Transferring to Skype – the connection is superb both
ways… (Which might explain why they got all those
billions while we are still in the garage).

I understand that Skype uses its clients as gateways
to transverse RTP when one client is behind such a
NAT. We can’t use this solution as we supply
commercial service and we can’t hook up to someone
else utility.

So, here comes the “big one”:

How do we overcome such a situation? 

Thanks for your help,

mik