I imagine that you can then solve those other problems one at a time by implementing alternatives in your webmail client. The interface to the user can stay the same, but you can add additional more secure transports underneath that the client can opt to use when there is indication that the person they are communicating with uses a mail system that supports that upgraded security solution. In the interface, you just need an indicator of what information is being leaked on a recipient by recipient basis.

At the end of the day this is how filesharing evolved... from FTP to Napster to Kazaa to Torrents to Magnet links. They slowly solved each of the attacks out there.