UPDATE: Actually, after doing everything I outlined the first time, I still met the "ssh_exchange_identification: Connection closed by remote host" error. I even tried various other things like running denyhosts --purge, and then restarting the denyhosts daemon. Actually, I tried lots of things that were proposed by members of various forums and wikis. 

What actually worked: Adding my IP address to /etc/hosts.allow

This is not the type of solution I wanted, but here's what worked.

All I had to do to be able to log in to my server was to hard code my IP address into the /etc/hosts.allow file.

That's it. I just put a line at the end of the file that looked like this:

sshd: 99.999.99.999

I just substituted 99.999.99.999 with my real IP addresss. 

After that, I had no problem logging in with SSH.

Old solution follows: (beware that this solution wasn't permanent)

It's no fun being locked out of your own server. 

I ran into this problem today where every time I tried logging to to the web server that hosts this site, I would receive the following message:

ssh_exchange_identification: Connection closed by remote host

That error doesn't mean a whole lot to me, and I'll spare you the details and just tell you how I was able to log in to my VPS again through SSH. 

All I really had to do was log in to my VPS using the out of band console provided by my VPS provider (if you don't have any other console access, use a web based file manager).

Once I got in, I took a look at the /etc/hosts.deny file. As expected, my IP address was listed in the /etc/hosts.deny file and that's why the SSH server was giving me the ssh_exchange_identification message.

No problem, all I had to do was remove the line from the /etc/hosts.deny file that had my IP address in it and after saving the file, I was able to log in via SSH without any problems. And I didn't even need to restart the SSH server.

That's the way I fixed it, and I'm pretty certain it would likely help you.