Eu nunca cheguei ao fundo de por que isso estava acontecendo. Falei com o apoio da empresa que fornece o servidor de e-mail smtp, que culpou a empresa responsável pelo endereço IP e vice-versa.
No entanto, usei o servidor de e-mail para gmail (smtp.gmail.com com SSL selecionado e porta 587, autenticação básica) e os e-mails foram enviados corretamente. [obviamente eu precisava abrir a porta 587 no firewall primeiro]
Depois fui mais além e configurei o gmail para usar as configurações originais do servidor de e-mail smtp, e isso também funcionou!