In order for two hosts behind two different NATs to be able to establish a P2P connection, they must both have each other's public endpoints (address/port). In order for each host to become aware of its own public endpoint, it can communicate with a known public server that returns to the host its public endpoint as seen by the server. See STUN (RFC5389).
In order for this mechanism to work, the NAT must consistently translate the same private endpoint to the same public endpoint regardless of the destination endpoint.
Would it be a good idea to implement a P2P application that depends on this particular NAT behavior (i.e. is it common enough)? Does Skype and/or other popular P2P applications have other fallback mechanisms?
EDIT: It looks like a NAT in which a different port is chosen per destination is called a "Symmetric NAT". In addition, some symmetric NATs increment the port number enabling a possibility of guessing the proper port.
Now I suppose the question is: Roughly what percentage of NATs are symmetric NATs, and what percentage of those use random port assignments vs. something like incrementing?