I've thought through it pretty well, and the basic idea is clearly sound. Here's my cut on the basic lookup method. I prefer to call the MD5 fingerprints "handles", since they are the keys actually transmitted in the protocol, and to call the full cryptographic public keys "cryptokeys" or something similar.

1. To query the system, I send a handle to any server that's willing to serve me, and it sends me back an IP address.
   
   
2. I contact the given IP address, and ask for a cryptographic certificate of authenticity and a public key used in that certificate. I check the certificate against the public key, and I hash the public key and check it against the handle. If both check out, I have confidence in the IP address.
   
   
3. If I get no answer from the IP address, I ask the server for the public key and certificate that it has stored. (Some caches may choose to keep only the handles and IP addresses). If I am not satisfied, I may hunt for another server that can give me the correct IP address.
   
   

I ran my own check on the birthday paradox calculation, and I am provisionally convinced (reserving a few repetitions to check for errors) that an accidental collision on hashed handles is acceptably improbable. But I'm not totally confident of security against an attack. To attack the system, a bad guy only needs to create a collision on a handle. We can defeat brute force attacks. But there are likely to be number theoretic attacks based on analysis of the combination of the public key system and the hashing method. Even though public-key cryptography based on pairs of large primes appears to be secure, there are number-theoretic attacks much more efficient than brute force. If there are similar attacks on MD5, then we may be unable to carry the security of long cryptographic keys over to shorter hashed handles. I checked the RFC on MD5 very briefly. It's not obvious that an attack on the use of MD5 to produce handles translates into an attack on its use to ensure the integrity of a file transfer, so even though it's well designed for its purpose, it might not be sufficient for the handle problem.

We must also keep in mind that handles are intended to live a very long time, and so we must prepare for security with much faster computers and unpredictable advances in number theory. Whatever method we choose now must survive for some decades, and then we must have a way to upgrade in place to larger keys and/or new cryptographic methods. Finally, since this is intended to provide handles to every person and decision-making organization in the world, there needs to be some serious help and guidance on key management.

In spite of these worries, I'm convinced that you've laid out the essence of the right sort of method for authenticating updates to the handle-IP tables. No matter how centralized the method, updates have to be authenticated by public-key techniques. And the key management problem is essentially the same with a centralized trusted source. But I'm not sure yet that the public-key/hash method avoids the need for a trusted central authority to associate a unique cryptographic key with each handle, in spite of malicious efforts to create collisions. Such a central authority may provide upgrade paths to stronger cryptography that are not feasible in a completely distributed system. If we depend on a central authority for the public-key/handle relation, then there may be no point in using the hash method. As far as I can see so far, the merit of letting the handle be a hash of the public key is that (assuming no collisions) it allows a queryer to get the public key from the owner of the handle, instead of from a server. In the presence of malicious collisions, the value of that particular relation between handle and cryptographic key is less, and perhaps not great enough to be worth enforcing.

ASAP I would like to get back to the strategic question: what does it take to start such a system? There is clearly a feasible solution, no more costly than the current DNS and probably less costly. It's a terrible shame that we don't have it in action. If we truly don't need a central trusted authority, the cost of startup goes way down, so this is worth pondering further.

BTW, I searched the RFC archive for anything on handles divorced from names, and came up blank. Such an idea must have been discussed at some point, I would think. If anyone can cite it, please do.