I got this issue when I tried to send email on my VPS using PHP, the app would report everything sent successfully, but nothing came. This fix is for Debian specifically, but will work with any Debian-based Linux OS that use the apt-get package manager like Ubuntu.
Read more here
It turns out that my VPS was configured with exim4, I dont know when I installed it, but it was probably included as a dependency somewhere down the line, but PHP wasnt feeling the love. So I went in and used apt-get to install postfix this automatically removed exim4 and installed postfix and configured it allowing me to use PHP to send emails.