First, I want to thank Falko Timme for the helpful article on setting up DenyHosts
for Debian. It was very clear and easy to follow. I got DenyHosts running in
no time.

After I got it working, I couldn't help but move things around to make it
more "standards-compliant". I didn't want to use the .deb package because it's still in testing and i'm using stable. So Here's how i went about it:

mkdir /var/lib/denyhosts
chown root:root /var/lib/denyhosts
chmod 750 /var/lib/denyhosts

Then modified /usr/share/denyhosts.cfg to include:
WORK_DIR = /var/lib/denyhosts

Run it once (to create the files inside $WORK_DIR) then:
chmod o-rwx -R /var/lib/denyhosts

mkdir /etc/denyhosts
chown root:root /etc/denyhosts
chmod 750 /etc/denyhosts
mv /usr/share/denyhosts/daemon-control /etc/denyhosts/
mv /usr/share/denyhosts/denyhosts.cfg /etc/denyhosts/
chmod o-rwx -R /etc/denyhosts

Also:
rm /etc/init.d/denyhosts
ln -s /etc/denyhosts/daemon-control /etc/init.d/denyhosts

and modify /etc/denyhosts/daemon-control to include:
DENYHOSTS_CFG = "/etc/denyhosts/denyhosts.cfg"

And finally:
chmod o-rwx -R /usr/share/denyhosts
chmod o-rwx /usr/bin/denyhosts.py

PS.
As I wanted to always run it with the --purge option i simply edited
/etc/denyhosts/daemon-control to include:
DENYHOSTS_BIN = "/usr/bin/denyhosts.py --purge"
 
et voila