That problem is partially solved by using a supernode overlay structure. It isn't particular elegant, and it relies on certain nodes being willing to work more for the network - but it can enable nodes behind a NAT to parcitipate relatively easily.
The point is that one has to have a very good reason to use a P2P architecture, as it tends to create problems.