проблема описана плохо...
если пытаться заниматься телепатией, то в первом случае ваш сервер предоставляет некорректный адрес (скорее всего адрес отправителя, например с использованием имени вашего внутреннего домена, который во внешней сети не является корректным).
Второй случай (а первый вполне может оказаться частным случаем второго) свидетельсвует о том, что IP вашего почтового сервера попал в черный список. Скорее всего некорректная настройка сервера позволяет его использовать в качестве открытого релея для внешних спамеров, либо кто-то из ваших внутренних пользователей грешит, либо действуют боты, залетевшие в вашу сеть.
Устраняйте причину и следуйте указанной ссылке, чтобы покинуть черный список.
