I feel like a lot of the things GPG aims to do are fundamentally hard. It's not the technology that sucks, it's the problem. I completely agree that the answer will come from thinking about user interactions first, but I'm not sure that the solution will look much different than a better GPG client.