Yep, Today was my day. Sometimes I forget to load my private key to connect with the server and I get rejected. This accumulates the authentication errors and ta da, I get locked out after the 3rd time. Denyhosts keeps track of the number of authentication attempts and adds the IP on the /etc/hosts.deny file.

DenyHosts is a script intended to be run by Linux system administrators to help thwart SSH server attacks (also known as dictionary based attacks and brute force attacks).
Bot's are scanning the internet and trying to make attempts to login. Take a look at your auth log file and you will see many attempts, with many I mean  many PER SECOND!

When I take a look at my /etc/hosts.deny file I see my own IP.  After removing my IP it will be put back with the next login attempt. What the hell?

Denyhosts stores the IP addresses also in these files listed below. Make sure you check them all and remove when necessary. 

But first stop denyhosts using this command

#Stop
systemctl stop denyhosts.service

#Start
systemctl start denyhosts.service

/var/lib/denyhosts/hosts
/var/lib/denyhosts/hosts-restricted
/var/lib/denyhosts/hosts-root
/var/lib/denyhosts/hosts-valid
/var/lib/denyhosts/users-hosts

Protip:
Always disable password authentication in SSHD. Instead use public key authentication. It's more convenient and more secure. But be careful with your private key.