[QRS]

Не могли бы Вы описать как Ваш Exchange отправляет наружу письма?

Вариант1:
сам по MX-записям... тогда вопрос: как сервер разрешает DNS-имена - сам Exchange (не знаю как в 2003, а в 2007-м можно настроить разрешение имен через конкретный DNS - при переезде это могло стать проблемой) или через собственный или внешний DNS (нормально ли они работают)?

Вариант2:
через relay-сервер провайдера... тогда: новый relay прописали? - провайдеры обычно блокируют relay из чужой сети.