So, you're right, the fact that email doesn't have a global directory is a feature. It's a feature that's underappreciated by a great many folks who've suggested alternatives to email that do rely on grand central unified directories.
Which suggests that an email alternative which has a similar directory-of-directories concept might stand a better chance.
I've been thinking along lines of clustered hierarchies of users, with various trust bases within them. If you wanted clusters of no more than about 50 neighbors (well within a Dunbar exhange), then a hierarchy 6 layers deep gets you to coverage of all of Earth's population (15.6 billion individual nodes). Deeper, cross-linked, or other structures could offer greater depth of address use for individuals.
I've also been wondering if perhaps national postal systems ought to take over electronic messaging. I can hear the screaming already, but with privacy-supporting protocols (including metadata), much of the risk might be mitigated. In particular, I'm interested in addressing the "who are you?" question -- identity, and re-establishing it, is difficult.
I'm thinking that a good reputation system, and perhaps a poll-and-fetch method, rather than a straight delivery, could make email much more resistant to spam.
Under poll-and-fetch, a sender would indicate that it has a message for another party. That party would then fetch the message, should it be interested. Fully vetted senders would have their content fetched automatically. Spam senders would have to sit on their spools and wait for (and support) many individual incoming fetch requests. Spammers identified as such would be identified through reputation systems.
Granularity of reputation might be at IP space, domain, mail host/peer, or individual sender basis.
For many sender/recipient pairs, a strong and clearly positive or negative relation would be established early. The hump is to become known as a trusted sender, for which some sort of trust seed or reputation vouching system might work. I'm still hazy on what might work there.
Mind that that cost can be met by some spammers, as it's effectively how a number of present online systems work. But in general, spammers tend to be taken down, and you remove the fire, cram, and forget mechanism of mail blasters, or the sparse, wide botnet model, where a given node emits only a relatively small number of messages.
Adding reputation to the mix strikes me as the secret sauce though.
I'd really like to see a further exploration of the concept. djb's essay is still only a very rough outline.
The greatest difference between email and all of today's proprietary alternatives is that your email identity doesn't need to be vetted by any central authority. Of course this makes spam harder to deal with, but it's part of the cost of decentralization and one that we must learn to deal with. Fortunately, most of the email services I use are pretty good at filtering spam, as well as making sure that my emails don't get marked as spam by other email services.