But this begs the question. How does the user get the public key and address of a node without connecting to a public directory? How does he know he's connecting to something trustworthy?
Given that context, you really just need the address of any node, not the address of a particularly "trustworthy" node, so you can get one from a friend's client or from a random website. We have discussed some alternatives, such as being able to put out a bounty on an existing peer-to-peer cryptocurrency blockchain (one which would have to not itself be fully blocked for you, of course). We also have been getting interest from some people in academia who have a number of other techniques, which again are mostly viable because of the background that "what if we can provide enough mitigations in the network itself and use what has been learned from blockchains to mean you don't need to find a trustworthy node".
As far as I've researched, I've not seen anything which would enable reliable NAT traversal which wouldn't also make the network traffic trivially identifiable.
STUN works only for certain types of NAT and requires servers which aren't behind NAT. TURN is an external proxy, so can easily be identified by monitors of the network.
The concept of Orchid seems nice but the actual implementation seems very hand-wavy.