Shot in the dark. If allowguest=no change it to yes. Or maybe NAT issue. Do you have port 5058-5062 open UDP? Not just 5060.
Instead of opening up individual IP’s have you tried just directing everything on 5058-5062 to your internal server? What type of firewall are you using? Does it have SIP ALG enabled or something? Have you tried using a different firewall?
The trick here is after all your “to no avail” steps fail, examine the underlying network you put in place,
from two separate ssh sessions, one from asterisk CLI
sip set debug ip (your target)
rtp set debug ip (your target)
this will give you a a raw network view of your SIP session as seen by your asterisk box, while you also from the other shell:-
tcpdump host (your target)
which will show you what is really happening. You should see packets on udp/5060 both ways as you try to make “contact” with your provider, if the Asterisk SIP conversation is one way, then correct your PNAT firewall.
once that is working then the rtp packets on some port within your /etc/asterisk/rtp.conf range, also bidirectional will be apparent, and not translated by your firewall.
When that traffic is seen both at the tcpdump level and the asterisk cli level, then it will work, if not, correct your PNAT firewall rules.
This all assumes that all your efforts to have Asterisk know about itself both locally and externally are correct as to your NAT settings, (you said they where)
If any of these sessions “time-out” then again fix your PNAT box to suit.