I decided to spend the day reviving project Nessie. I was pretty successful!
I started from scratch with the goal of making Nessie's inner workings significantly simpler. Nessie now uses OpenDHT to bootstrap the service (see OpenHash vs. Your Mother) and XML-RPC to communicate. Another simplification is that Nessie doesn't do any routing! All connections are direct connections over (eventually) SSL encrypted HTTP channels. It should be possible later to have nodes act as proxies to get around firewalls, but I'm in no hurry.
To test the new system out, Nessie currently is capable of chat through a console interface (I exaggerate, it's really just a Python interpreter).