Denyhosts executes the program given through PLUGIN_DENY for every host already in hosts.deny, not only for the ones newly added. This is an upstream bug (s. http://sourceforge.net/tracker/index.php?func=detail&aid=1734736&group_id=131204&atid=720419) but upstream seams dead for a while. Attached you find a proposed patch which works for me.
Created attachment 186631 [details, diff] Patch for PLUGIN_DENY functionality
(In reply to comment #1) > Created an attachment (id=186631) [details] > Patch for PLUGIN_DENY functionality > Can you attach your patch to the upstream bug, please?
+*denyhosts-2.6-r6 (23 Sep 2012) + + 23 Sep 2012; Pacho Ramos <pacho@gentoo.org> +denyhosts-2.6-r6.ebuild, + +files/denyhosts-2.6-daemon-control.patch, + +files/denyhosts-2.6-defconffile.patch, + +files/denyhosts-2.6-foreground_mode.patch, + +files/denyhosts-2.6-hostname.patch, +files/denyhosts-2.6-plugin_deny.patch, + +files/denyhosts-2.6-single_config_switch.patch: + Include multiple Fedora and Debian patches that also provide a fix for plugin + deny behavior (#264165 by Christoph Erdle). +