> I'm not aware of any entirely decentralised system which would allow two computers which are behind NAT to find and then talk to each other. Or any obvious design which would work there.

I think the GNUnet has some stuff in it which can even work across different protocols, e.g. hopping across TCP/IP over Ethernet to Bluetooth to packet radio. It has some neat stuff where, as I recall, it probes out a random path, then tries to get at its intended destination, remembering successful attempts. It definitely sounds cool, but it's not currently in an end-user-usable state.