Eu encontrei a solução para esse problema. Estou usando o msmtp , que é um proxy SMTP e funciona similar ao sendmail, assim, ao tentar enviar um email, o comando msmtp é chamado de php com sintaxe similar ao sendmail.
Agora, o comando msmtp será executado pelo mesmo usuário em que o apache2 está sendo executado. No meu caso www-data.
Existe um arquivo de configuração para o msmtp (/etc/.msmtp_php no meu caso) que precisa ser legível pelo usuário do www-data.
O motivo pelo qual o CLI estava funcionando e o Apache PHP não, é que eu estava executando o CLI sob root, que tinha as permissões corretas para o arquivo, mas o apache2 está rodando em www-data, que não tem essas permissões.
So the solution is: chown the /etc/.msmtp_php file to www-data:www-data and chmod the same file to 0600, otherwise, msmtp will complain about loose permissions.