Read this post: SIP Port Forwarding - #3 by lgaetz
Do the channel originate test noted therein using your working trunk. I will bet that the test fails for you. You have configured your router for a specific SIP use case, one that works for the majority of calls using one provider but not another. With only two data points and success with one but not the other, your mistake is in assuming there is something at fault with the non-working provider. If you went out and chose 20 more providers at random, you would see similar problems with about half of them. It is not the service that’s at fault here, it’s your router configuration. There is almost nothing that can be done at the PBX to compensate for router/firewall misconfig.
Not sure which docs you refer to here, but this is just not true. I would guess the majority of SIPStation customers are behind NAT, and unless they are using a Sangoma SBC, they are by definition behind a third party router/firewall. The service works fine if the firewall is configured correctly.