Написать postmaster'aм и спросить в чем дело.
Может они и не блокировали тебя

спасибо, за совет. Только как же им написать, если соединения с этими серверами не устанавливается?:)

да, напишу с какого-нибудь yahoo-шного сервера

В общем проблема в моем сервере, а точнее в работе DNS-сервера. На примере одного из тех почтовиков, которые отказывают моему в соединении, я выяснила следующее:
на том домене два MX-сервера с приоритетами 0 и 10. Так мой сервер посылает почту на MX-сервер с низшим приоритетом-10 и он ему отказывает в соединении. Интересно, что пару дней назад почта шла на их MX-сервер с высшим приоритетом(0).
Настройки DNS-сервера уже не менялись долгое время, а обновление коренных зон производится еженедельно.
В чем тут может быть дело?

Твой-то собственный hostname корректен? A то был у меня случай, когда
один докапывался по поводу того, что его почтовик не пущают либо письма
от него не доходят. А все из-за того, что завел он в локалке левый
домен и пытался от его имени общатся с внешним миром. А его и рубили,
с сообщением unresolvable.:-)) Но судя по тому, что раньше у тебя все
работало, это не тот случай.
Что конкретно пишет sendmail в логах, когда пытается отправлять почту?
Может банально из-за загруженности не дожидается приветствий от
удаленный стороны и отваливается с timeout. Попробуй увеличить
задержку в sendmail.cf.
В любом случае - расскажи что пишет.

Нет, левых доменов у меня не прописано.
Сначала каждое письмо у меня обрабатывается avpkeeper`ом и статус этой операции "Sent". Потом передается сендмайлу и тут уже статус "Defered:Connection refused by [remote_mail_server]".
Еще начались какие-то проблемы с avp: avpkeeper уже пару раз писал, что не может связаться с avpdemon`ом. Я перезапускаю демон, и снова работает все, кроме посылки писем на те проблемные домены.

Информация к размышлению:
похоже, что мой сервер неполюбили только некоторые сервера.
Попытка telnet remote_IP 25 отвечает refused, а с другой машины ок, есть прилашение sendmaila.
И еще, сканирование nmap`ом, с опцией -v, показало что remoteIP ок, но ВСЕ порты закрыты, а вот -sS, дал следующие порты 25, 53, 110, 113.
Вроде бы этим серверам, как и всем другим, я насолить не долна была, релейнга нет, и спама не должно было быть, в Mail Abuse Prevention System LLC, который по умолчанию использует sendmail, мой IP тоже не значится. Чудеса да и только!

P.S. на днях я перешла на новое ядро 2.4.2, но ведь это не долно было сказаться на работе Sendmail`а и AVP?

Значит, все-таки насолила, вольно или невольно.
Может, там начинающие админы и они каждую попытку
прислать на их домен письмо воспринимают как попытку вторжения :)))
Если эти сервера в твоем городе, то найди в whois их координаты и
позвони, если не хочешь писать им.
Или просто не обращай внимания. Все само собой разрешится со временем :)

Проблема отсылки писем разрешилась

Проблема разрешилась, но появились новые вопросы...:)
Дело в том, что проблема снялась после того, как я вернулась к старой версии ядра - 2.2.12-20, и сразу все письма на проблемные сервера ушли.
В новом ядре я навключала практически все, что относилось к новым возможностям NAT, и вот не настроила все должным образом.
Кстати, у тех проблемных серверов nmap`ом не определялся тип операционки.

Ну вот видишь, сама с фильтрацией напортачила. Займись iptables.
Желаю удачи.

Некоторые сервера проверяют имя хоста по ай-пи. И если не резолвится, отказывают в приеме почты, поскольку прямая зона днс не может существовать без обратной. Обратись к провайдеру, пусть делегирует обратную зону.