Acontece que postfix e sendmail estavam sendo executados ao mesmo tempo. Algo ocasionalmente fazia com que o serviço postfix fosse iniciado, o que fez com que o status sendmail saltasse para dead but subsys locked .
Pensei que tinha verificado que postfix não estava em execução executando sudo service --status-all . De maneira bastante confusa, o processo principal para postfix está listado como master not postfix . Ao analisar a saída de sudo service --status-all , esperava ver postfix (pid xxxx) is running... e, como não havia essa linha, assumi que postfix não estava em execução!
Para corrigir isso, simplesmente executei sudo service master stop seguido por sudo service sendmail restart e tudo está bem novamente. Agora é hora de rastrear o que está causando postfix para iniciar de vez em quando ...