>sendmail с недавнего времени при установлении соединения происходит таймаут от 30 с
>до 1 минуты. telnet заходишь и до приглашения
>220 Sendmail ...
>проходит столько времени.

Тайм-аут либо DNS, либо ident. И если время каждый раз разное, больше похоже на DNS.