Такая ситуация может возникнуть если твоего сервера сервер получателя по NsLookup запросу не находит. То есть у тебя на DNS твой сервер должен быть прописан и в прямой и обратной зоне.
Сей час в целях борьбы со спамом почти все сервера у тебя в таком случае не будут принимать почту.
Зайди на
www.all-nettools.сом и проверь определяется ли имя твоего сервера по IP (окошко NsLookup).