Lesson of the day:
If you are running Debian or Ubuntu and you have Exim4 configured with a smarthost, chances are that your mail delivery for phpmail will fail.
The fix, find and edit /etc/php5/apache2/php.ini
sendmail = /usr/sbin/sendmail -t -i
Make sure at the end of the sendmail line you have that magical -t -i. Without them, it won’t work with Exim4 as your MTA.