Urukhayy

mail() - отправляется с локального сервера, не нуждается в наличии почтового сервера
smtp - можно как с локального так и с удаленного, необходим почтовый сервер. Можно использовать GMAIL и другие (проверять нужно, не помню). Например хост: smtp.gmail.com, логин example@gmail.com (ваш почтовый ящик) и пароль от него, порт и так далее.

стандартной функции mail() вам хватит с головой, просто нужно проверить ваш IP в спам базах и настроить SPF запись для домена (что бы не было проблем с доставкой)

1. Покупаем VPS
2. Ставим Ubuntu 12.04
3. Ставим ISPmanager
4. Включаем нужные плагины и компоненты
5. profit

imho самое простое решение решение:
1) Сделайте себе отдельный домен с которого вы будете отправлять рассылки, уведомление, итд.
2) Подключите его к pdo.yandex.ru , создайте там почтовый ящик с которого будет идти рассылка.
3) Дополнительно подключите его к https://postmaster.yandex.ru/
4) Настройте DKIM и SPF записи help.yandex.ru/postoffice/security.xml
5) Используйте любое решение для php которое умеет отправлять почту через smtp (например swiftmailer)

В принципе вместо яндекса можно использовать любую почту по вкусу.

Процентов 99.9%, что у Вас PTR-запись отсутствует...
И соотв. все такие письма считаются спамом автоматом.

что из первого пришло в голову, что почта отправитель в данном случае sdfds@mail.ru, имеет ip адрес отличный от адреса вашего сайта, такие письма майл ру игнорирует. Вам надо создать на хостинге почтовый домен и указывать его при отправлении.

Он их спамом скорее всего считает, пользуйтесь phpmailer или swiftmailer с ними доходит