Tim:
Being behind NAT and/or a firewall does mean you'll need to use a VOIP provider. If you had none of them in your way, or complete control over them, you could run as your own service (the same as how people run their own web and mail services, for instance).
Thufir:
This is where http://en.wikipedia.org/wiki/IAX would come into play, as a workaround?
Yes, and no. Yes, you could do something like that when your network is entirely yours to control. No, I'd probably call it a solution, rather than a workaround. ;-) I'd call *having* to be a peer on someone else's VOIP network a workaround to networking problems.