You are right, it is installed.
I created a PHP page of phpinfo(), and saw that mail is invoking "/usr/sbin/sendmail -t -i". When I ran that from the command line, I got the following error:
sendmail: fatal: chdir /var/spool/postfix: Permission denied
It appears my user didn't have rights to go to /var/spool, it was granted to root:telnetd.
I ended up solving the issue by adding my web user (the user the web site is running under) to the telnetd group, log out, log in, and lo and behold, I could run /usr/sbin/sendmail.
I sent a test email from PHP, and all worked out great. I don't know if this was something specific to me and my PS (I didn't change anything to cause this), but hopefully it helps somebody else down the road.