Re:I tried S/MIME (Score 1)

Thawte issues free personal X.509 certificates for use with S/MIME. The previous poster was correct: the facility you want already exists, and it's already present in some of the most commonly-used clients - Netscape, Outlook and Outlook Express at the very least.