Я сам последнее время склонился к мысли об использовании сторонних сервисов для отправки писем.
Например, mandrill.com. У них там всё настроено и они сами заинтересованы, чтобы письма доходили. Для пробы отправлял на gmail, yandex, mail - везде доходило без проблем. На своей стороне использовал PHPMailer.
Спам через них рассылать проблематично, так как имеются ограничения.
