As mentioned above: Are you sure sendmail is installed on the system? It's possible that there could be a different MTA installed on the system (such as qmail, postfix, exim). Most other MTA's will create a symlink /usr/sbin/sendmail which points to some other binary. This is done for backwards compatability with sendmail. You might want to check whether /usr/sbin/sendmail is a symlink. If so, where does it point to?
Since you are using PHP, another workaround may be to use phpmailer. You can use phpmailer to send outgoing messages through a remote mail server using SMTP authentication (on port 587 if necessary), bypassing whatever local MTA is installed on the system altogether.