How could they possibly solve it? One of the most important features of Google Mail is fast searching of e-mails. For them to search e-mails, they need to be able to index them so they can't just encrypt the emails on their storage.

Frankly, for me the abilty to search my emails quickly outweights the risk of some nosey Google employee with a shallow private life reading my private email or bank stuff or whatever.