Письма, отправленные от другого mailserver в сети, отклоняются (привет был отклонен),

Лучшее предположение - то, что HELO Вашего почтового сервера не настроен правильно - должно быть полностью определенное доменное имя (например, mx077.example.com), и похоже, что Вы просто используете mx072.

Я не знаю много о exim, но если это - проблема затем, этому уже ответили: Когда exim4 отправляет HELO/EHLO, как я настраиваю, какое имя хоста он отправляет?