Delirium, в подобных случаях надо смотрет полный лог SMTP-сессии. Для начала. И не совсем понятен смысл подключения телнетом на свой сервер и попытка отправки на проблемный сервер. У тебя Open Relay?
Проверять телнетом надо, подключаясь со своего сервера на проблемный.
ugara, у вас релеев нет на маршруте? Сервер напрямую отправляет сообщения? Покажите кусок SMTP-лога для этого сообщения и результаты телнет сессии.
