Enigmail: Recipient not valid, not trusted or not found

There are 2 way to solve the problem:

1. (more secure)
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.

2. Go to OpenPGP → Preferences → on tab «Sending» check «Always trust user ID»