Необходимо адрес вашего smtp сервера корректно зарегистрировать в DNS, у него должны быть записи:
PTR MX
Начните отсюда:
http://ru.wikipedia.org/wiki/DNS
Появятся вопросы - задавайте.
Заодно, проверьте наличие IP адреса вашего сервера в блэк-листах - он вполне мог там оказаться.
