From emailselfdefense.fsf.org:
Be wary of invalid keys
GnuPG makes email safer, but it's still important to watch out for invalid keys, which might have fallen into the wrong hands. Email encrypted with invalid keys might be readable by surveillance programs.
In your email program, go back to the first encrypted email that Edward sent you. Because Edward encrypted it with your public key, it will have a message from Enigmail at the top, which most likely says "Enigmail: Part of this message encrypted."
When using GnuPG, make a habit of glancing at that bar. The program will warn you there if you get an email encrypted with a key that can't be trusted.
What exactly are invalid keys? Are these keys that have been revoked?