First, the problem exists only if both users are behind symmetric NAT of if one of them has symmetric and the other port-restricted. In both cases is impossible to establish a peer-to-peer connection between them. But if one user is symmetric and the other full cone, then there is not a problem.
The solution with symmetric is to use an intermediarie machine called TURN that is a forwarder that receives packets from Alice and forward them to Bob and viceversa. Skype uses supernodes (nodes with public IPs) as TURN nodes.