TLDR is: Distributed (as in DNS) directory with append-only entries keyed by hash-of-email and third party replication/validation/logging.

Discussion of spam implications at https://moderncrypto.org/mail-archive/messaging/2014/000727....

Widespread encryption could be a recipe for Google (as the largest of the proposed directories) sliding in an identity reputation scheme (eg. based on location / communications history) and brokering it as a service.