Ok, now this issue is present even withouth the hidden recipient gpg option. This means that if a user is 
1. using gpg with 2 private "Encrypt" keys
2. using evolution to view his mails
3. getting mails encrypted to the more recent "Encrypt" subkey
reading encrypted mails will always fail. Even though you are prompted to enter your password for this subkey. running gpg from cli works fine here again.

Emails encrypted to the older "Encrypt" subkey won't fail.

Hm, reason for this issue is that evolution uses gnupg 1, but not gnupg2. The GPG key is only available to the gpg2 installation, not to gpg 1.
While running `$ gpg2 --decrypt message.mbox` works fine, running `$ gpg --decrypt message.mbox` fails with the same error message as evolution: "Could not parse PGP/MIME message: Failed to decrypt MIME part: Secret key not found"

So the solution should be to make evolution use gpg2 instead of gpg1. If this should be configurable, please prefer gpg2 over gpg1 due to issues reported above.

There was a git commit which should (in theory) fix this issue by preferring gpg2 over gpg:
https://git.gnome.org/browse/evolution-data-server/commit/?id=7a73cb2
but it looks like this doesn't work. See also a bug report closed with this commit: https://bugzilla.redhat.com/show_bug.cgi?id=1055598

So in comment #0 one step to reproduce is missing: You need to have both gpg 1.x and gpg 2.1.x installed and have your subkeys (at least some of them) created with gpg2 version ≥ 2.1.0.

There is one functional difference between gpg and gpg2: gpg uses a secring.gpg file to store the private key, gpg2 doesn't use this file but stores it somewhere else. So if you create a key or subkey with gpg2 ≥ 2.1.0, this key will not be visible to gpg 1.x.

To work around this issue you can export your secret key (plus subkeys) from gpg 2.1.x and import it into gpg 1.4.x. In theory, running `gpg2 --export-secret-subkeys | gpg --import` should fix this issue, but gpg won't do that, it tells me my private key hasn't changed (which is wrong). If I delete (make a backup!) the ~/.gnupg/secring.gpg file before running the command above it works fine.


To reconstruct the steps to reproduce (hopefully precise enough this time):
1. have both gpg 1.x and gpg2 2.1.x installed
2. create a private key with gpg 1.x
3. create private subkeys with gpg2, expire private subkeys created with gpg
4. send and receive emails encrypted to your new key
5. open evolution and try to read them

What happens:
Evolution still uses gpg instead of gpg2 to decrypt emails. This will fail since private subkeys are only known to gpg2, but not to gpg.

What should happen:
Evolution should always prefer gpg2 over gpg if installed, then decryption works fine.

Additional info:
Encryption of emails always worked with my new subkey.

When watching evolution call gpg, it call gpg (not gpg2) with these parameters:

--verbose --no-secmem-warning --no-greeting --no-tty --batch --yes --status-fd=[number] --verify /tmp/evolution-pgp.[random] -

--verbose --no-secmem-warning --no-greeting --no-tty --status-fd=[number] --command-fd=[number2] --decrypt --output -

The git commit I noted above was later reverted. See https://git.gnome.org/browse/evolution-data-server/commit/camel/camel-gpg-context.c?id=457febfa55b3cc34b2aa91eaa92e80b28b7674d6 and https://git.gnome.org/browse/evolution-data-server/tree/camel/camel-gpg-context.c#n471

Probably https://wiki.archlinux.org/index.php/GnuPG#Unattended_passphrase is helping to fix this issue.
Recent versions of gpg2 (I am running 2.1.9) with gpg-agent keep the passphrase in memory, so the reason for reverting this commit is gone.

Symlinking /usr/local/bin/gpg to /usr/bin/gpg2 works fine for me.

Thanks for a bug report and all the investigation around. There were reasons to prefer gpg2 over gpg and then take it back to prefer gpg over gpg2. The problem with keys is that, as you found, the gpg2 and gpg do not store the keys at the same place, thus what is available in one gpg is not available in the other. Another problem is that different applications use different gpg. I was told that for example seahorse uses gpg2, which makes evolution-data-server "incompatible" with keys generated in seahorse.

See bug #745050 comment #11 and below.

I'm changing the default to gpg2 again. I hope for the last time now.

Created commit 4297d8b in eds master (3.19.90+)
Created commit 8e3a484 in eds gnome-3-18 (3.18.5+)