I worked on VoIP before RFC3489. We built our own ways to handle NAT and firewalls, but it always involved something like a directory server that would see both

I worked on VoIP before RFC3489. We built our own ways to handle NAT and firewalls, but it always involved something like a directory server that would see both your private and public IPs and share information between clients at call time to connect calls.