spurious "connect: Host is unreachable"

[Urs Hoelzle]

On our network we see the following phenomenon: whenever a connection to a
remote host is built, the first connection attempt will fail, giving the
message "connect: Host is unreachable".  If retried within a couple of
minutes, it will always work.  This happens with mail, ftp, telnet, rlogin
etc.  The behavior is reproducible and is the same on all our machines
(Sun3/4s, SunOS 4.0.3, some diskless, one name/yp server).

Typical example:

otis> telnet next.com
Trying 129.18.1.2 ...
telnet: connect: Host is unreachable     <-- this msg comes w/no delay
telnet> quit
otis> !!
telnet next.com
Trying 129.18.1.2 ...
Connected to next.com.

Subsequent connects will work if made within a couple of minutes of a
successful connect.  What is happening here?  It seems that inetd (or
something else) times out too quickly during the connect, but why?

Any help is greatly appreciated.

-Urs