Seu amigo está enviando seu e-mail usando a opção "destinatário oculto", que remove o ID da chave do destinatário dos metadados do OpenPGP. Isso é usado para privacidade adicional (o destinatário não está mais contido nos metadados), mas força o cliente a iterar sobre todas as chaves privadas disponíveis. Esconder o destinatário parece um pouco mais cauteloso para o e-mail comum: o destinatário do e-mail deve ser armazenado com o correio, de qualquer maneira (se você quiser que o e-mail seja entregue).
Mas isso deve ser bem suportado pelo Enigmail. Certifique-se de que suas chaves privadas estejam disponíveis em gpg --list-secret-subkeys
e gpg2 --list-secret-subkeys
para garantir que você não tenha diferentes conjuntos de chaves disponíveis entre as diferentes versões do GnuPG (eles podem estar usando locais diferentes para armazenar suas chaves privadas).
Caso contrário, peça ao seu amigo para enviar e-mails sem usar o recurso de destinatário oculto.