ssh_exchange_identification: Connection closed by remote host

This sometimes happens on my long-running RHEL4 server that has lot of ssh traffic. It happens unexpectedly, and no log entries are produced.
As mentioned in The Site With the Lamp, this seems to be a problem with too much (old?) ssh connections.

But the solution recommended there (waiting) is usually not meeting my needs, I need an immediate solution.
/etc/init.d/sshd restart does not work, but a simple
killall -9 sshd
followed by a
/etc/init.d/sshd start
saves the day!