We are experiencing exactly the same issue. I am pretty sure we are doing things properly.
I am writing this lines because we have this problem with an only device. We have five devices being tested with the same program, each device with a different provider. Some of them get public IPs and other NAT IPs. But this behaveour it only occurs with a certain provider and an special APN to get a public IP.