Yeah, when I mentioned the ability to associate email addresses with public keys, I wasn't very clear. I did't mean regular email addresses, but was actually thinking of bitmail-only email addresses. Perhaps ones based on Namecoin .bit domains.
But I wasn't suggesting interop with existing email infrastructure, this would be completely separate. In fact, the idea would be to disrupt and supplant the regular email we all know and love, at least for some use cases where privacy is paramount.
Everyone would have their bitmail client which they could use to send encrypted email, as well as their regular Gmail addresses and whatnot. Most people have multiple emails anyway, this would just be one more.
One nice thing about bitcoin, which would carry over to bitmail, is that despite the core technology (the official client) being completely outside and orthogonal to the current financial system, it's very easy to use for its fundamental purpose. Sending and receiving bitcoins is just simple. I envision the core bitmail client would work similarly and be similarly simple. No need for interop as long as there are specific optimal use cases for it (say, Arabs and others coordinating against oppressive regimes, stuff like that).
I think you could perhaps make it work with a bridging service between the networks?