This is one of the questions of the FAQs of DenyHosts and you can find it here.

To save you a click, the relevant section of the page says, as of Jan 21, 2010:

If you have been accidentally locked out of one of your hosts (because DenyHosts has added it to /etc/hosts.deny you may have noticed that simply removing it from /etc/hosts.deny does not in itself correct the issue) since DenyHosts keeps track of the attempts in the WORK_DIR (/var/lib/denyhosts by default) files. In order to cleanse the address you will need to do the following:

1.  Stop DenyHosts (”sudo /etc/init.d/denyhosts stop”)
2.  Remove the IP address from /etc/hosts.deny
3.  Edit WORK_DIR/hosts and remove the lines containing the IP address. Save the file.
4.  Edit WORK_DIR/hosts-restricted and remove the lines containing the IP address. Save the file.
5.  Edit WORK_DIR/hosts-root and remove the lines containing the IP address. Save the file.
6.  Edit WORK_DIR/hosts-valid and remove the lines containing the IP address. Save the file.
7.  Edit WORK_DIR/users-hosts and remove the lines containing the IP address. Save the file.
8.  (optional) Consider adding the IP address to ”’WORK_DIR/allowed-hosts”’
9.  Start DenyHosts (”sudo /etc/init.d/denyhosts start”)

Note: Not all of the WORK_DIR files will contain the IP address so you may want to use grep to determine which files contain the IP address.

Here is a list of commands for copy-paste:

1. sudo /etc/init.d/denyhosts stop

2. sudo vim /etc/hosts.deny

3. sudo vim /var/lib/denyhosts/hosts

4. sudo vim /var/lib/denyhosts/hosts-restricted

5. sudo vim /var/lib/denyhosts/hosts-root

6. sudo vim /var/lib/denyhosts/hosts-valid

7. sudo vim /var/lib/denyhosts/users-hosts

8. (optional)

   sudo vim /var/lib/denyhosts/allowed-hosts

9. sudo /etc/init.d/denyhosts start