se usi il comando mail() su linux php si appoggia proprio a sendmail ( che deve essere installato e configurato correttamente ).

Una soluzione semplice semplice è utilizzare smtp dalla libreria phpmailer.

http://phpmailer.worxware.com/index.php?pg=examplebsmtp

In questo caso dovebbe funzionare senza mail server installato.