All the encryption stuff with emails is "secure" as long as you can establish the link between identities and public keys. The actual cryptography and format is already implemented by most platforms, following the S/MIME standard, which is fine as these standards go (even the mail application in iOS 5 knows S/MIME). S/MIME normally relies on X.509 certificates.
At some point, there must be a procedure for ensuring the link. The concept of identity of a user is not part of the "computer world". Usual procedures entail a physical meeting between the key owner (the user) and a sworn official who performs the actual validation. This is expensive, this is hard, and this is not necessarily what we want: do we want to bind the public key with a legally defined individual or with whoever controls a given email address (for some appropriate notion of "controls") ? As usual, the difficult part is deciding what we really want with enough precision.
When the link is established, the information can be conveyed through certificates. Certificates have the nice benefit of being transport neutral: since they are signed, they can be obtain by whatever means without any security issue. This avoids having to trust your "central repository". Standards and protocols are ready for that: X.509 is approaching some level of maturity, and the central repository is known as "the Directory". The Directory can be thought of "One LDAP Server to rule them all" (in practice, the LDAP protocol has emerged as a subset of the access protocol for the Directory). There is a minor setback, which is that the Directory does not exist: it is a central, worldwide structure, and such things do not appear unless a clear need for it is found (for instance, the DNS exists because without it, the Internet would be a harsh place; but encrypted emails do not yet have sufficient political push to trigger the apparition of the Directory).
X.509 is meant for hierarchical trust management, which is appropriate for business, and would also be good if we want to use "legal identities" (your name and existence as a citizen are defined by the State which recognizes you as one of its own, and you cannot get more hierarchical than that). For loosely bound communities with a spirit of good-humoured anarchy, a Web of trust might be more adequate (but, though decentralized, the WoT implies more network traffic because trust comes from redundancy of the certification topology). One characteristic of the WoT is that it entitles every user to act as a registration authority: a RA is whoever does the "physical world" steps of verifying the identity of a user (as Tradition goes, in a bar over a pint of Guinness). The OpenPGP format contains the bells and whistles which support WoT management (it could be done with X.509 -- everything can be done with X.509, with extensions -- but the details of WoT with X.509 have not been completely worked out yet).
The "everybody is a RA" is a way to sidestep the issue of defining the notion of identity you want to achieve: every user decides what notion it uses, when emitting the certificate for someone else (signing his public key, in OpenPGP terminology). The bad side of it is that when using a public key obtained from the WoT, you do not really know what you get. The public key has been verified to be linked with... what ? It is not said.
An interesting system is Identity-Based Encryption. It is very lightweight in that it does not need a central repository of public keys at all: the public key of a user is his identity (his name, his email address...). But this still dances around the issue: IBE allows you to use as "identity" whatever can be encoded as a human readable string, but most notions of identity are still bound to the physical world ("I want to send an email to that guy") and there must be non-computer parts in the system.
Summary: for security of encrypted emails, the problem is not support software (it is already there), protocols (we have them) or central repository (the pieces are ready, it just needs to be installed on actual servers -- or, we can do without a repository by using IBE). The problem is deciding what notion of identity you want to use, and setting up the parts of the identifying procedures which are not in the computer world at all.
(Many people around the World seem intent on transferring their lives into their mobile phones. This may ultimately "solve" the problem: we no longer need to send emails to human beings, only to smartphones, and these are computers. I am not sure I want to live in such a world, though.)