Yay, I like this topic...
I have always thought that there really needs to be some trusted third-party verification service for Bitcoin addresses, which would work in a similar fashion to an SSL CA. I don't believe the pgp-style web-of-trust model gives enough guarantees (or has enough defense against bad actors (edit,
CACert is pretty close)) and using a cryptographic solution invites namespace-collision problems (i.e. the super secure third-party escrow solution at casacius.com.)
You would in practice also have a network of trust providers such that no one player has any control over the system. Bitcoin applications would operate similar to the
perspectives project and pull trust information from many providers.
This is a straightforward way to get a useful protocol going. Simply add Bitcoin-OTC metrics, add a dash of GPG sigs, and toss in some IRL identity verification, and you'd be there.
Add thanke's or etotheipi's method on top for more security and anonymization.
--
This was my old favorite solution to this problem. But wow, from
retep's work with creating fidelity bonds and thinking about it a lot more I have spent the last couple of hours fleshing it out into an entire system, and I have a new favorite.

Instead of hijacking the thread here which I can be prone to doing I have written this up on another thread in Alternative Currencies:
Repcoin: a decentralized reputation currencyIt would be a good candidate solution for this problem.