That's a doozy, could be anything.
If it's possible, the next time your server disconnects and refuses connections can you do a :
ssh -v -v -v -v hostwhereSshStoppedWorking
and also (if you can, since running sshd in verbose mode makes it run single threaded and die after the connection closes)
on the sshd server that's refusing the connects, kill all you sshd's and run
/path/to/your/sshd -v -v -v -v
and connect from the original host
Then post both of those outputs to this thread. That might show us something that will ring a bell.