I recall reading that you could make P2P connections work behind a NAT by having an external server route the connections initially. Is this not true, or does it only work in some circumstances?

This is the "nat traversal techniques don't work all the time" caveat, especially with TCP.

It often works, a common method is called “UDP hole punching”.