Our network is split by a Firewall.  The machine in question (beta) is   
outside of the Firewall.

I connected to several other machines, outside of out Firewall, and   
telneted back to beta and got connected instantly.

So,  all machines behind the Firewall connecting to beta, are having to   
wait 20 - 30 seconds for a connection.

All machines outside the Firewall connecting to beta, are getting   
connected instantly.

When I watch beta's processes via ps -maux, I see that sendmail is   
hanging in startup mode for 20-30 sec. before going into server mode,   
accounting for the delay, with machines inside the Firewall.  Machines   
outside the Firewall put sendmail immediately into server mode.

So does sendmail, some how, try to verify the connection to the DNS   
lookup?

BTW, I've already checked DNS problems, nslookup is okay.

jam