copy this to a text file and name it "test.php"
<?php
phpinfo();
?>
and load it on your server and call it up in your browser.
then search for the term MAIL and see if it provides a sendmail path... (i know you said you dont use it...) but it's worth a look
if all else fails.. you could use smtp...