This may not be a performance issue, but I have something like 110,000 ips blocked in
hosts.deny (2 years of denyhosting). Should I ever clear
hosts.deny? Does anyone have any experience with what happens when you do so?
It's safe to remove them. Depending on your version of denyhosts, there may be a provision to purge old entries. You can either zero the files or remove them and restart the daemon.
If you remove the file, it will most-likely be repopulated with the entries from your online /var/log/secure.* - say, the last week or 5 weeks, depending on your daemon config.
I've had older versions of denyhosts slow down considerably as the blocked IP tables grow.
Are you using any of the advanced denyhosts features like the centralized reporting or at least email notification?