Alternatively, you can look at using X.509 certificates. Most of the major and commercial dedicated email clients support this (even the one on iPhone). Though you are SOL if you use GMail's web browser interface.

You may need to pay for certificates, though CACert or maybe StartSSL will give you free ones.