I think a better system could be publishing a triple (name, keyfingerprint, current-server) on a shared datastore (e.g. DHT). The user doing the search would still need to find some out-of-protocol way to identify the right person, though.
EDIT: Kadmelia on Emule is a working implementation of a similar system to what I described, but for files instead of users.
cjdns has a simple approach: your tcp6 address is your public key. This the right idea. Leverage what you already have that is unique (not to imply IP address is necessarily truly unique, e.g., anycast).
But in general to be on the network, you have to at least one unique item: your network address. So leverage that to make other unique identifiers.
To encrypt communications, you may need to maintin encryption keys. So leverage them to be part of each peer's unique identifier on the network.
Connecting to strangers, and only using the network to get each and every bit of infromation from the outside world, is all fine and good, but this sort of peer-to-peer networking is much more valuable with peers who you can identify in person. Without using a computer. You can exchange all the above numbers (identifiers) on business cards.
Secondly, it ties you to them; what happens if you switch servers, or ISP, or whatever? I mean, right now I'm planning on switching to a cheaper, faster offer from another ISP, but I wouldn't do it if I were to lose all access to my accounts on the different services.
I think the id should be both controlled by the user and portable; that mostly leaves public keys and their fingerprints as ids.
They could shut you down, but I don't think they could pretend to be you since they don't have your private key..
The best solution that comes to mind now is building a server with a database of all the users and their respective servers. But, of course, that would break the decentralized purpose of Tent. It's an interesting problem to solve.
EDIT: Another big problem, how do I search users? A DNS-like solution would be feasible?