Well, those guys at Nullsoft have released another p2p application, W.A.S.T.E., and I've been checking it out. They released the C++ code for it, but I don't know C++, so I've begun hacking out the protocol in C.
The documentation says that, when you have a potential host to connect to, WASTE connects, and sends 40 bytes to the other host, which consists of (if there is no network name), 16 random bytes, as well as 24 more bytes which is a blowfish of the random bytes with a 20-byte SHA-1 of my public key plus 4 pad bytes. If the remote host knows my public key, it sends a 40 byte response.
I used Ethereal to sniff a send to a host running WASTE that has my key to get a 40 byte send. I sent that send to the host and also get a 40 byte response. In the C++ code, I see that g_pubkeyhash is the 20 bit public key hash encrypted, and that WASTE uses (a possibly modified version of) Paul Kocher's Blowfish code. So I'm messing around with this for now. The source I'm reading is in C++, a language I don't know, so I guess I can be forgiven for not totally understanding it. I often wonder how much faster I would be at writing code if I had years of experience under my belt. Much faster, I guess.