A drop down menu in each contact could specify which key to use for mails to this person. The drop down could also contain the options "undefined" and "no encryption". Available keys should have trust indicators (stars, colours) to indicate the quality of the keys for the average user.
To get it totally user friendly, add some tooltip explaining how to enhance the trust level (by key signing) and automatically download new keys from key servers in the background.
Smart selection of a key by the key-id in the PGP mail header would be awesome