Because by all accounts, judging by the Wiki Entry, usign a public server is not really a wise thing to do in production .... the " http://dumbme.mbit.com.au/trixbox/stun_servers.htm" link on teh Wiki is broken, and the Wiki also says "Note: stun.fwd.org is gone; also stun.freeswitch.org is never guaranteed to be up and running so use it in production at your own risk.".... so I can only assume that most public servers are similarly provided on a "best endeavours" basis and prone to disappear at any time. Further, I now have an IPsec VPN between me and the firewall, hence eliminating NAT concerns, and I am still seeing the same issues as originally described with things partially working (even with Any/Any rules applied to firewalls).
Why not pick up a public stun server and config it in your softphone, most likely it will address your issue.