У "нормального почтового домена" domain.ru во внешнем мире прописаны MX-записи? Скорее всего нет, судя по ответу мэйлру...
Как проверить - из Windows:
запустить nslookup и ввести команды:
> set type=MX
> domain.ru 8.8.4.4
Server: UnKnown
Address: 8.8.4.4
Non-authoritative answer:
domain.ru MX preference = 10, mail exchanger = mx.yandex.ru
8.8.4.4 - публичный DNS Google (он отвечает всем и достаточно корректно)
mx.yandex.ru - имя почтового сервера, по которому он должен быть доступен извне
domain.ru - то, что в адресе отправителя идёт после разделителя "@"
Из Linux примерно то же самое, но запускать надо "nslookup - 8.8.4.4" и в запросе домена не указывать сервер.
Если MX для домена не указан, то править внешний DNS (у провайдера, у регистратора, или на своём сервере - в зависимости от собственной специфики).
Кроме того, для совсем уж правильной работы, необходимо указание обратной зоны - это только через провайдера решается.