Если вы используете версию gpg старше 2.1.0, проблема может заключаться в алгоритме шифрования CAST5, который выдает сообщение, не защищенное MDC.
Enigmail с версии 2.0.4 не расшифровывает такие письма: https://addons.mozilla.org/en-US/thunderbird/addon/enigmail/versions/
Решение состоит в том, чтобы обновить gpg. Чтобы читать старые письма, используйте параметр --no-mdc-warning как «Дополнительные параметры для GnuPG» в настройках Enigmail (вкладка «Дополнительно»).
edit: из Enigmail 2.0.5 этот обходной путь не работает. Последние новости можно найти на форуме Enigmail (например, как исправить ваш открытый ключ, если он слишком старый): https://sourceforge.net/p/enigmail/forum/support/thread/03ebee57/