Tanto per cominciare bisogna vedere se i tuoi siti girano su host Linux/Unix o Windows.
Nel primo caso, PHP usa il programma sendmail o equivalente, che deve trovarsi sulla stessa macchina. Se non riesci a spedire le email vuol dire che il programma non c'è, oppure PHP non lo trova per problemi di path. Oppure per qualche motivo il pgm non permette a PHP di spedire le email.
Se invece sei su win, la funzione mail() va a collegarsi ad un server SMTP indicato su php.ini.

In conclusione:
- per prima cosa, posta l'errore che ricevi
- poi esegui un phpinfo(), e guarda il valore di SMTP se sei su win, o di sendmail_path se sei su linux