Всё просто.
1) У вашего IP должна быть обратная DNS-зона. Погуглите.
2) В настройках домена, с которого шлёте письма, должна быть правильно настроена SPF-запись
Для хоста: @
Тип: TXT
Значение: v=spf1 a mx include:_spf.yandex.net ~all
v=spf1 - это версия протокола
a - можно слать письма с IP, который совпадает с A-записью
mx - тоже самое, только почтовые сервера
include:_spf.yandex.net - подключает почтовые IP от Яндекса, если юзаете Яндекс почту для домена.
~all - исключая (запрещая) всё остальное. Т.е. со всех остальных адресов - это спам.
Если вы шлёте с локальной машины и у вас IP адрес провайдером постоянно меняется, то тут ничего поделать нельзя. Письма либо вообще не будут доходить, либо валится в папку спам (в зависимости от того куда шлёте и жёсткости спам-фильтров сервисов).
Если вам провайдер даёт статический IP, то просите сделать вам обратную DNS зону для нужного вам домена через суппорт!
Причём домен обратной DNS-зоны (например myhomedomain.com) не обязательно должен совпадать с доменом с которого шлёте почту (mysenddomain.com) - суть в том, чтобы обратная DNS-зона у вас была в принципе.
Например у LeaseWeb при заказе VPS обратную DNS-зону можно вписать самому.
В своём ответе уверен на 100% =)