Another possibility is ident. Some servers use ident for reverse lookups. If ident is being dropped at the firewall, this will cause a delay. You can shorten this delay by adding a rule to reject ident (as opposed to drop), which will time ident out much quicker.
You can turn that off by modifying /etc/xinetd.d/telnet and commenting out the line that reads:
log_on_failure += USERID
If ident is the problem the telnet connections will establish quickly and you'll get a logon prompt after at most 30-40 seconds (DNS lookup delay). If that solves the problem we'll have to look at how to turn off ident for the other services.
You can turn that off by modifying /etc/xinetd.d/telnet and commenting out the line that reads:
log_on_failure += USERID
If ident is the problem the telnet connections will establish quickly and you'll get a logon prompt after at most 30-40 seconds (DNS lookup delay). If that solves the problem we'll have to look at how to turn off ident for the other services.