In thinking about the GMail encryption problem, I came to realize that for ordinary users liable to forget their passwords, it would not be suitable to tell them after such an event that all their email archives are forever lost. This means some sort of Key Escrow. Not the nasty kind done with the clipper chip, but one done voluntarily.
I came up with a system I call Friendscrow. (I suspect others have also thought of the same thing.) This is a ZUI (Zero User Interface) system, at least for normal operation.
Your key would be broken up into some number of fragments, say 20. The fragments would be arranged so that getting any 10 of them recovers the key, but getting fewer gets you no closer.
The system would search your mail logs to find your 20 most frequent correspondents in the system. (It has to be a big and popular system for this to take place, otherwise some UI is needed.) Most of these will be your friends, a few may be enmies. Techniques would be used to eliminate mailing lists, etc. If you want to add basic UI, you might scan and approve the list.
The key fragments are then distributed to the 20 close contacts. They will not know this has been done, the fragement will just be placed in their files, encrypted with their key.
If you lose your key (or when you die) you use your friends to get it back. You mail those you know to be your closest correspondents a special message. It says to them, "You may not know it, but you may have a fragment of my lost key. Go to the system and click on the link to help a friend recover a password."
The link explains that you should first confirm you are really talking to the friend through some other means than e-mail. Or confirm that they are dead. It will ask you to confirm they are not under duress. Then it will give you the fragment to hand over to the authorized person.
You should be able to find half the fragments, which would be enough to get back your key, and read your archives again.If you don't have enough correspondents who are in the same system as you, you would have to email them the key. The email would just tell them to store the key in a safe place, possibly encrypting it if they do that sort of thing. Unfortunately this mailing, if tapped into, would allow somebody to get your key unless your friends take encrypted mail -- a rare event, unfortunately.
They would have to save the mail, which is some UI but not too much. If they are on the same system as you, as noted above, they are not even aware they hold your fragment until they go looking for it.
Is this what GMail needs? Probably not. They can probably do the job by paying professional escrow agencies in different countries, or offering different levels of escrow security depending on user need. This system has the advantage of being free, and leaving it in the hands of your friends rather than a stranger.
To make it more secure, you could encrypt the key fragments using a special crytographic technique called an identity certificate. In this scheme the recipient can only decrypt after they prove to a special agency that they really own a given e-mail address. This protects you from having the key broadcast listened in on, but puts your friends to more work, and might be subject to a warrant.