I understand why this is happening. My ssh-agent is sending multiple keys to the server, and only one of them is good. So it hits the max number of login attempts on the server and disables the login. I know how to fix this from the clientside. However I do not know how to fix this from the server side. So even when my client sends only the one key, I get the failed login attempt. I've tried restarting the service, but that doesn't work. Also all of my google searches talk about how to resolve this from clientside, so my googlefu has failed me. Is there a blacklist that I need to manually edit or something like that?
Having a lot of keys in agent is not a good idea. Much better is to define the connection between keys and servers in your .ssh/config, which will avoid such problems. For example:
Host myhost myhost2 IdentityFile ~/.ssh/id_rsa_myhost Host myhost3 myhost4 anotherhost IdentityFile ~/.ssh/id_dsa_another