Писал уже в более ранних ветках. Посмотри-не перекрыт ли у тебя ident (порт 113). Если в ipchains/iptables стоит DENY-поставь REJECT. Ещё тормоза возможны при DNS-запросах. Я сейчас сходу не помню название опции, но можно задавать время тайм-аута на AUTH-запросы. В файле sendmail.cf пропиши Timeout.ident=0s.
Были мы на тех граблях...<br> У меня проблема решилась исправлением работы DNS. Особенно если sendmail >= 8.11.xx. Сброс таймаутов череват долгим лежанием в очереди...