Se você estiver usando a versão gpg anterior à 2.1.0, o problema pode estar no algoritmo cifrado CAST5, que não produz mensagens protegidas pelo MDC.
O Enigmail da versão 2.0.4 não descriptografa esses e-mails: link
A solução é atualizar o gpg. Para ler emails antigos, use o parâmetro --no-mdc-warning como "Parâmetros adicionais para o GnuPG" nas preferências do Enigmail (guia avançado).
edit: do Enigmail 2.0.5 esta solução não funciona. Para obter as últimas notícias, consulte o fórum do Enigmail (por exemplo, como corrigir sua chave pública se ela for muito antiga): link