Naming service for the Invisible Internet Protocol

I have had trouble falling asleep tonight, and as a result I had the idea described below. After thinking about it for some time, I have concluded that I2P (the Invisible Internet Protocol) will benefit from a naming service application (hereafter NS).

As currently specified in the protocol, communication between two destinations can occur only if one knows how to contact the other. In other words, the first destination will have to know the second's IP address or hash to communicate. This information will have to be given to the first destination beforehand. What if the destination is not known, but I know that I want to contact a certain person and establish an instant messaging session?

The NS application, running over the I2P network, would solve this problem. For example, user1 wants to speak with user2 via Instant Messenger. user1's IM client would look up user2 in a name server, and obtain the corresponding contact information. If user2 does not have IM capabilities, the NS would tell user1 this. Users (or entities, rather) who wanted to simplify being contacted by others would, at their option, register with a name server, where others could look them up. Now, instead of having to type in user2's IP address, user1 could type in "user2:im" as the destination to connect to (or "user2:www", as another example).

The naming service would have several capabilities. Entities could register with it (possibly paying hashcash for the service), add records for services they provide at their destinations (IM, WWW, NS, etc.), and modify and delete these records. Records would be signed with an established public key so that only the entity establishing the record could modify it. A record would contain the following data:

Name of the entity
Public key for entity
Hash( Destination ) for contact purposes
List of services or applications one can connect to at that destination.

If anything I said above is unclear, please ask questions. The idea needs development, but I believe that applications running over I2P would benefit from a NS application.