When someone (for instance Antton Rouget) advertises that they are able to receive encrypted email, how to proceed ? The first step is to ask for the email to be encrypted, via the Options menu:
Ideally Evolution would try and fetch the key from public key servers, but it does not and will display an error message instead:
Failed to encrypt: Invalid recipient <firstname.lastname@example.org> specified. A common issue is that the gpg2 doesn’t have imported public key for this recipient.
To solve this problem, the key must be fetched from public key repositories. It is the purpose of the Seahorse which can be found by pressing the Windows key and entering seahorse in the search field:
Clik on the Remote menu, select Find remote keys, enter the email and click Search.
Be patient, it can take a while. If there are no results after a few seconds, close the window and try again. Two consecutive search will not respond in the same way and the servers are frequently overloaded. When the result shows, right click on the line and select Import.
Again, it can take a while to fetch the key from the servers and trying a few times is a valid strategy to workaround the problem if the import fails with an error message after a minute or two. There is no progress bar displaying progress but it does not mean the request stalled.
It is also necessary to instruct Evolution to trust the GPG keys imported, via the menu Edit => Accounts => Mail Accounts => The email from which you send mail => Edit => Security. And check the Always trust keys in my keyring when encrypting option.
Ideally all this would happen automatically but for now it has to be done manually.