If denyhosts needs rsyslogd, shouldn't it be a dependency?
It doesn't need rsyslogd specifically. A virtual dependency on syslog with multiple providers including rsyslogd and syslog-ng might be a possible solution. However denyhosts itself is pretty outdated and everyone should switch over to fail2ban anyway.