I had this same problem using t-mobile's internet3 APN (VPN data plan) which gives a routable (but firewalled) IP address. I was able to get this to work by adding this to my extensions.conf for my phone:

qualify=5000
qualifyfreq=30

I use 5 seconds for the qualify timeout because I got tired of seeing in my logs that the phone was lagged. The change in frequency is needed since if the packet is lost, the sip udp connection could timeout which appears to be the cause of the problem.