Eu encontrei um plug-in para o qpsmtpd chamado tnef2mime. Ele foi originalmente projetado para converter anexos TNEF (winmail.dat) da Microsoft em MIME, mas também converte mensagens UUEncoded. Eu não consegui encontrar uma fonte canônica para este plugin, mas Servidor SME mantém o plugin em sua distribuição e o banco de dados de bugs implica que as pessoas o estão usando recentemente.
Então adicionei qpsmtpd a um pequeno servidor Ubuntu que estou usando para outros propósitos, extrai o tnef2ime do RPM, habilitei-o como um plugin e agora estou enviando meus problemáticos clientes SMTP através desta caixa primeiro.