A version of your suggested solution is currently in use in Estonia [1], although it is not really used to encrypt e-mails.

I guess it's one of the virtues of having a population a tad smaller than 1.5 million.

[1]http://en.wikipedia.org/wiki/Estonian_ID_card