Enigmail: Recipient not valid, not trusted or not found
There are 2 ways to solve the problem:
Sign recipient’s key with yours:
OpenPGP → Key Management → select key, right-click on it and select «Sign Key»
If you’re not ready to tell the whole world that you trust this User ID, make Local (non-exportable) signature: it will be stored in your keyring only.
Go to OpenPGP → Preferences → on tab «Sending» check «Always trust user ID»