A resposta veio de um artigo da Base de Conhecimento Comodo: Erro de certificado não confiável no Android .
A causa do erro são os certificados Comodo existentes no armazenamento de certificados padrão do Windows. Um dos certificados intermediários, o COMODO RSA Certification Authority , está presente por padrão na pasta Autoridades de Certificação Raiz Confiáveis como um certificado de CA de auto-emissão. Eu não instalei lá, o Windows tem em uma instalação de estoque. Não sei por que está lá, porque a verdadeira Autoridade de Certificação RSA da COMODO é emitida pela AddTrust, não por ela mesma, e as impressões digitais não combinam. Além disso, este falso auto-emitido Comodo Root CA não está presente no armazenamento de raiz do Android 4.4, embora existam três outras Comodo CAs com CNs similares o suficiente para serem confusas, a menos que você verifique as impressões digitais. Talvez haja algum motivo histórico relacionado à reorganização de CA entre Comodo e AddTrust.
A solução do artigo da KB corrigiu o erro em K-9: remova a Autoridade de Certificação COMODO RSA auto-emitida das Autoridades de Certificação Raiz Confiáveis do Windows (na verdade, recortei e colei em uma pasta diferente no caso de precisar reverter a alteração, em vez de excluí-la permanentemente).
Esse certificado falso fez com que o MDaemon assumisse que o certificado Comodo intermediário de nível superior era na verdade um certificado raiz e não o enviou no handshake SSL para o K-9. Isso foi indicado, mas não ficou óbvio o suficiente para mim na saída s_client. Antes da correção, o MDaemon só enviava os dois certificados inferiores da cadeia, e o Android não tinha um caminho de confiança do terceiro certificado (Comodo Domain Validation) para AddTrust, porque o segundo certificado estava faltando na resposta. Após a correção, o MDaemon enviou os três certificados inferiores da cadeia, e o Android conseguiu encontrar um caminho da Comodo Certification CA para a AddTrust.
Um item não resolvido são as atualizações automáticas da CA raiz do Windows. Comodo avisa que essas atualizações irão restaurar o certificado indesejado no armazenamento da CA Raiz Confiável e recomenda que você desative todas as atualizações da CA raiz. Acho que essa não é a melhor solução porque quero que a lista de CAs raiz fique atualizada com essa única exceção. Eu estou pensando em tentar encontrar ou escrever um programa que pode excluir um determinado certificado do armazenamento de certificados do computador e ter que executar periodicamente. Talvez haja um script baseado em PowerShell ou certmgr.exe que eu possa escrever. No mínimo, talvez eu possa adicionar algum monitoramento automatizado quando a lista da CA raiz for atualizada e o certificado indesejado for restaurado, então sei que é hora de excluí-lo manualmente.