Da ich aufgrund der gleichen Symptomatik, nach einer Google-Recherche auf diesen Beitrag gestoßen bin, möchte ich noch hinzufügen wie sich das Problem bei mir letztendlich lösen lies.
Der Hinweis, dass OpenPGP in den Konten-Einstellungen unter Ende-zu-Ende-Verschlüsselung aktiviert sein muss, bzw. dass dort der zu verwendende Schlüssel ausgewählt sein muss, ist schon mal gut.
In meinem Fall sollte aber gar nicht die die primäre Adresse des Kontos, sondern eine weitere Identität (dienstleistung@firmendomain) verwendet werden, die beim Antworten auf eine andere E-Mail bereits automatisch vorausgewählt war. Der passende Schlüssel für diese Identität war bereits importiert und gültig, aber er musste der Identität noch unter Konten-Einstellungen ... -> "Weitere Identitäten..." -> "Bearbeiten..." -> "Ende-zu-Ende-Verschlüsselung" zugewiesen werden. Danach wurde automatisch OpenPGP als Verschlüsselungstechnologie ausgewählt und korrekt verschlüsselt und signiert.
Man muss also neben den Einstellungen für das Konto selbst auch alle verwendeten Identitäten auf die korrekte Schlüsselzuweisung überprüfen.