I've found the solution to this problem. I'm using msmtp, which is an SMTP proxy and works similar to sendmail, thus, when trying to send a mail, the msmtp command is called from php with similar syntax to sendmail.
Now, the msmtp command will be run by the same user apache2 is running under. In my case www-data.
There is a configuration file for msmtp (/etc/.msmtp_php in my case) that needs to be readable by the www-data user.
The reason CLI was working and Apache PHP was not is, that I was running the CLI under root, which had the correct permissions for the file, but apache2 is runnuing under www-data, which didn't have those permissions.
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.