Возможно такое, что у хостера есть правило: можно отправлять письма только от отправителя, который зарегистрирован в веб-почте хостинга. Т.е. сперва надо зарегистрировать пользователя почты. Например: no-reply@ваш_домен.com. Потом в заголовках отправляемой письма указать эти данные.

$to = 'nobody@example.com';
$subject = 'the subject';
$message = 'hello';
$headers = 'From: NO-REPLY@ваш_домен.com' . "\r\n" .
    'Reply-To: NO-REPLY@ваш_домен.com' . "\r\n";

mail($to, $subject, $message, $headers);