Are there better solutions?
Yes.
Skype uses the Hole Punching trick.
Assume A wants to contact B:
A and B are connected to server C
server C tells B to send dummy UDP packet to A ( to IP and port used by A for Skype connections) effectively punching a hole in it's own (B's) firewall
this packet is discarded by A (it goes from outside of the NAT) but now A can send UDP packets to B which will let them through firewall ( B router thinks this is a response to [dummy] packet)
This article describes it with more details: How-Skype-Co-get-round-firewalls