Mail.ru + php форма обратной связи. Почему не приходят письма?
Почта Mail.ru считает, что у них настолько крутой антиспам фильтр, что может позволить себе "выкидывать" некоторые письма мимо папки "Спам" и мимо "Корзины".
Вы можете попробовать побороться с их саппортом, а когда надоест, подключите pdd.yandex.ru и отправляйте письма через smtp. (Вот отличный класс: PhpMailer - берите оттуда 2 файлика class.phpmailer.php и class.smtp.php).
Можете сделать удобную обёртку для него, типа: 
class Mail {
    public static function send($email, $subject, $html, $text)
    {
        $mail = new PHPMailer;

        $mail->isSMTP();
        $mail->Host = 'smtp.yandex.ru';
        $mail->SMTPAuth = true;
        $mail->Username = 'user@domain.tld';                 // SMTP username
        $mail->Password = 'myBestP4ssw0rd';  // SMTP password
        $mail->SMTPSecure = 'ssl';                            // Enable TLS encryption, `ssl` also accepted
        $mail->Port = 465;                                      // TCP port to connect to

        $mail->CharSet = "UTF-8";

        $mail->From = 'user@domain.tld';
        $mail->FromName = 'My Project';
        $mail->addAddress($email);     // Add a recipient
        $mail->addReplyTo('support@domain.tld', 'My Project Support');

        $mail->isHTML(true);                                  // Set email format to HTML

        $mail->Subject = $subject;
        $mail->Body    = $html;
        $mail->AltBody = strip_tags($text);

        if(!$mail->send()) {
            return false;
            // $mail->ErrorInfo;
        } else {
            return true;
        }
    }
}

Ну и не забудьте подключить для вашего домена DKIM и SPF записи. 
Теперь ваши письма никогда не попадут в спам!

P.s. Да, в соседнем ответе посоветовали mandrill. 
Объясняю, чем он хуже. 
Например, на gmail через яндекс.smtp письма приходят почти моментально. Через smtp mandrill они идут секунд 20-30, а иногда и минуту.
Кроме того, mandrill преобразовывает все ссылки в письме и переадресовывает через свой трекер. В то время, как яндекс - это просто почта без всяких понтов и параноидального слежения.
В общем, уведомления - яндекс.
Массовые рассылки - mandrill.

Upd (спустя 3 года):
Вижу, что мой ответ отметили решением, поэтому хочу пояснить, что ответ устарел. 

В настоящий момент smtp от Яндекса вижу как не самое лучшее решение по двум причинам:
1. У Яндекс PDD есть ограничение (и оно очень маленькое) на отправку писем в час и в сутки. Причём подробности этих ограничений вы не найдёте (публичная информация о лимитах не соответствует действительности; я сталкивался с ошибками отправки уже после 50 писем в час). Поэтому для нормальных массовых проектов эта почта не подходит. Только для хобби-проектов с невысокой активностью.
2. В целом у SMTP-протокола есть ограничения (он медленный). 

Для себя лучший вариант я нашёл в виде Amazon SES. Это такой шлюз отправки писем именно для уведомлений. Отправлять можно как через SMTP, так и через API. Причём у вас будут очень высокие пределы прежде чем с вас Amazon начнёт брать деньги (или это будут копейки). Недостаток SES в том, что для вывода домена в продакшен нужно будет написать в поддержку, объясняя зачем и как ты собираешься его использовать.
Вы можете попробовать побороться с их саппортом, а когда надоест, подключите mandrill.com и отправляйте письма через smtp.