I'd give it time. People won't enter their public keys when booking a flight, but it might be associated with their email address automatically. I could see Google running a service like Keybase. Or even integrating it further into whatever the next hip "online identity" service is. Built in privacy would be a huge boon.
The flight company (or email sender they use) could then request your public key and send off your message. And with some common protocols and APIs the complexity could be largely abstracted away.
I wouldn't underestimate the technology. When you look at more complex systems like internet routing tables, these problems feel a lot more solvable. We already have the technology for most of this. The problem right now is making it accessible.