Ok, problem's fixed. I think it was DNS. I tried all our DNS servers but all 
had problems with getting nameserver lookup deferred with sendmail. So I just 
installed a DNS cache server on the machine, and now it's all perfect. 
Basically, it's a DNS server that runs on 127.0.0.1 and then I pointed 
my /etc/resolv.conf to use that local server. The local server uses our office 
DNS servers, but it's more robust and also caches the results. As soon a I put 
this thing on, all the pending email whooshed right through. Could this still 
be looked into with that in mind?

I have the exact same problem (host name lookup failures), but (so far) only
with mail going to hotmail.com. And, as far as I can tell, all mail going to
hotmail.com is affected:

   [hotdog@mona ~]$ /usr/sbin/sendmail -bp
                   /var/spool/mqueue (11 requests)
   ----Q-ID---- --Size-- -----Q-Time-----
------------Sender/Recipient------------
   g272kX320367     2249 Thu Mar  7 03:54 MAILER-DAEMON
                    (Deferred: Name server: mx07.hotmail.com.: host name lookup
f)
                                          <ssssss>
   [...9 more emails going to various hotmail.com-addresses...]
   g24FZu225755      191 Mon Mar  4 16:35 <bbbbb>
         8BITMIME   (Deferred: Name server: mx06.hotmail.com.: host name lookup
f)
                                          mmmm
   [hotdog@mona ~]$ 

[Email-adresses have been obscured to protect the innocent]

However, I have no problem looking up hotmail.com, both the normal way and with
type=mx:

   [hotdog@mona ~]$ nslookup
   Default Server:  dns1.cybercity.dk
   Address:  212.242.40.3
   
   > hotmail.com
   Server:  dns1.cybercity.dk
   Address:  212.242.40.3
   
   Non-authoritative answer:
   Name:    hotmail.com
   Addresses:  64.4.45.7, 64.4.52.7, 64.4.53.7, 64.4.54.7
             64.4.43.7, 64.4.44.7
   
   > set type=mx
   > hotmail.com
   Server:  dns1.cybercity.dk
   Address:  212.242.40.3
   
   Non-authoritative answer:
   hotmail.com     preference = 5, mail exchanger = mx10.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx11.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx12.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx13.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx14.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx15.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx01.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx02.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx04.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx05.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx06.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx07.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx08.hotmail.com
   hotmail.com     preference = 5, mail exchanger = mx09.hotmail.com
   
   Authoritative answers can be found from:
   hotmail.com     nameserver = ns1.hotmail.com
   hotmail.com     nameserver = ns2.hotmail.com
   hotmail.com     nameserver = ns3.hotmail.com
   hotmail.com     nameserver = ns4.hotmail.com
   mx10.hotmail.com        internet address = 64.4.49.135
   mx11.hotmail.com        internet address = 64.4.49.199
   mx12.hotmail.com        internet address = 64.4.50.7
   mx13.hotmail.com        internet address = 64.4.50.71
   mx14.hotmail.com        internet address = 65.54.232.7
   mx15.hotmail.com        internet address = 65.54.232.71
   > 

Also, I can telnet directly to mx02.hotmail.com:

   [hotdog@mona ~]$ telnet mx02.hotmail.com 25
   Trying 64.4.55.135...
   Connected to mx02.hotmail.com.
   Escape character is '^]'.
   220-HotMail (NO UCE) ESMTP server ready at Fri, 08 Mar 2002 01:26:57 -0800 
   220 ESMTP spoken here
   QUIT
   221 Service closing transmission channel
   Connection closed by foreign host.
   [hotdog@mona ~]$ 

Only sendmail can't seem to make the connection :-(.

For what it's worth, I'm using RedHat 7.0 (kernel 2.2.19-7.0.12 on an i486) with
sendmail-8.11.6-2.7.0.

Looks all more like Internet problems or DNS issues. Please reopen if you can
point at any wrong code within sendmail.

Thanks,

Florian La Roche

This happens on Redhat 7.2 AND on skipjack. DNS failures are occurring, but dig,
host, etc resolve the domains fine. There seems to be a problem in sendmail.

I too solved the problem by installing a DNS caching server on our system. The 
problem appears not to be with sendmail as such, but with hotmail being 
_really_ impatient at some times.

Try to telnet to one of the hotmail-mx-servers on port 25 and pretend to want 
to send an email. Unless you cut'n'paste your commands, you'll get 
disconnected - as far as I can tell only for being too slow.

Sendmail appears to be make some dns-lookup(s) after it connects to 
mx__.hotmail.com (or any other server), and the dns-lookup)s= needs to happen 
really fast or hotmail will disconnect the sendmail-process. Therefore, a local 
DNS caching server will help. Well, at least from the second time, you try to 
send an email to hotmail, since the caching server still needs to make a lookup 
the first time :-).

I installed a DNS caching software to solve the problem. In this case, the 
problem is related to sendmail on the Linix machine sending out. The example 
given of Hotmail.com may be unrelated. By the time your Linux machine has been 
able to connect to hotmail.com's MX servers on port 25, it's already completed 
the DNS lookup. The problem is getting the DNS lookup to work succesfully. Once 
you've made the port 25 connection, everything's fine.