I have three and sometimes four VoIP adapters operating behind my router (plus soft phones), and some of them are reached directly -- i.e., without using proxies.
Are you saying the provider system refuses to recognize NAT? Or that your ATA is unable to be set to recognize its behind NAT??

I know on one of my ATA's, I believe its A Grandstream, that one setting can influence that behavior at the carrier side...