As in all systems, things will go wrong, whether it's your own bug or someone else's. Your system needs to not only be stable in the steady state, but to be able to return to the steady state when something interrupts it.
Protocol: we used a custom psuedo-TCP protocol built on UDP based on libjingle from Google (used in Google Talk): http://code.google.com/apis/talk/libjingle/file_share.html. Libjingle's filesharing itself was a decent resource for learning some P2P stuff as well.
NATing and routing: we used Skype's UDP hole punching: http://www.h-online.com/security/features/How-Skype-Co-get-r....
Skype configures each install to be a supernode by default and then disables it based on certain criteria (low speeds, behind a NAT/firewall, etc.). Discovery of other network nodes is an entire subject unto itself and a lot of other network discovery protocols are well documented; our system used a central server to track up-time statistically and map clients to one another based on finding a good fit. Happy to answer any questions here or at my e-mail address in profile.
"An Experimental Study of the Skype Peer-to-Peer VoIP System" http://saikat.guha.cc/pub/iptps06-skype/