Non-standard host.deny you describe at http://denyhosts.sourceforge.net/faq.html#aux (with empty BLOCK_SERVICE) is incompatible with non-empty PURGE_DENY because according to tcp_wrappers source code can't have # comments at all! It is read as single white space separated line, so any word from your comments is taken as the host for matching which is very dangerous from security point of view, moreover no diagnostic issued. You can check what happens here with tcpdchk(8) utility from tcp_wrappers.
DenyHost should stop with loud diagnostic when non-empty PURGE_DENY is used together with empty BLOCK_SERVICE.
Better fix will be to keep timestamps out of hosts.evil in your own directory and write only hosts and no comments to hosts.evil.