OCSP war eine gute Idee, war aber scheinbar nicht die Ursache. Danke für den Tip.
Ich habe zum Zugriff auf den Mail-Server mal KMail eingerichtet, und der hat kein Problem nachdem ich die CA ins KDE Systemrepository importiert hatte. Da OpenSSL auch kein Problem hat, dürfte die Problematik bei icedove liegen.
Mal eben ein anderes Zertifikat mit anderer CA zu generieren ist nicht so leicht, da z.B. der Mailserver wieder per SSL auf LDAP unter derselben CA zugreift.