$email = mb_convert_case($_POST["email"], MB_CASE_LOWER, 'UTF-8');
$message .= "<p>Текст письма</p>";

$headers = "MIME-Version: 1.0\r\n";
$headers .= "Content-type: text/html; charset=UTF-8\r\n";
$headers .= "From: site.ru <noreplay@site.ru>\r\n";
$subject = "=?UTF-8?B?".base64_encode("Тестовое письмо")."?=";
mail($email, $subject, $message, $headers);

Странная вещь... на yandex.ru, gmail.com письма уходят, а вот на mail.ru, list.ru bk.ru нет. Причем судя по логам даже нет попыток отправки.

В недоумении! Что может быть?

з.ы. ip нет в черном списке (хостер утверждает)