OK, here's an idea then. I've just made this up and I don't doubt there are flaws in my logic, but if I can think of something that might even half work, then I'm sure if we put our heads together, we can come up with something that fully works. It's not rocket science!
And for the record, all the following avoids needing to use a huge centralised database / certificate /identity repository.
Secure Transit
--------------
This is simple to address. We all have private/public keys. If someone wants to send me an email, their email server asks my email server for my public key. Using that, the sender (1) determines whether who they are talking to really is who they think they are talking to and (2) encrypts his/her email to me (using my public cert) and sends it on its merry way to me. While they're at it, they could sign their email with their private key so that when I receive it, I can verify that it did indeed come from the person I think it did.
This is simple, very well understood, and could even be supported by extending the current SMTP protocol, and indeed SMTP already supports encrypted transfer via TLS. To extend this to individual email accounts we could do something like...
HELO
THIS_IS_ME sender@example.com <senders public cert>
(reply from my email server is "ok" or "bugger off")
CERT_REQUEST rich@example.com
(reply from my email server would be "bugger off" or <rich's public cert>)
Authentication
--------------
That's already addressed (above) - the sender passes their public cert to my email server and from this, my email server decides whether or not to allow the email to be sent
New Senders
-----------
This is a trickier problem. How does the sender send me an email if I don't already know them (and therefore don't already have a copy of their public cert, and therefore can't say for sure whether I want to receive email from them or not)? And how do we do this WITHOUT having to rely on some "tree of trust" or some such?
One answer (or one collection of answers) could be...
I could apply some rules to my server so that when it receives a "THIS_IS_ME" command over the SMTP, and I don't already know the sender, I could reject the email outright, allow it in but flag it internally to say it is untrusted, etc etc. This wouldn't stop SPAM though without also (probably) stopping legitimate email. I could maybe improve the situation my adding more complex rules. One option may be to extend the "THIS_IS_ME" command to something like :-
THIS_IS_ME sender@example.com <senders public cert>
I'M_A_MATE_OF <someone I already know> and here's a signed recommendation from them <sender's info signed by "someone I already know">
If my email server is happy with the recommendation then it'll allow the email in
If the sender doesn't know any of my mates and so can't get a recommendation from them then we have a further problem. One crude answer (if the rules-based filtering method doesn't wash with you) could be :-
THIS_IS_ME sender@example.com <senders public cert> <sender's "small intro message" asking to speak to me>
(reply from my email server is "bugger off" or "I don't know you, but I'll read your "small intro message" and let you know if I will accept your email. Try again in a couple of hours if you don't hear back from me)
Of course the "small intro message" would be just that - simple text, and only just long enough to say hello. Not big enough to send a virus or a jpeg of a naked Latvian turnip farmer, etc.
I'll shut up now.