É seguro removê-los. Dependendo da sua versão do denyhosts, pode haver uma disposição para limpar entradas antigas. Você pode zerar os arquivos ou removê-los e reiniciar o daemon.
Se você remover o arquivo, ele provavelmente será repovoado com as entradas do seu /var/log/secure.* online - digamos, a última semana ou 5 semanas, dependendo da configuração do seu daemon.
As versões mais antigas do denyhosts diminuem consideravelmente à medida que as tabelas de IP bloqueadas aumentam.
Você está usando algum dos recursos avançados do denyhosts, como o relatório centralizado ou, pelo menos, a notificação por e-mail?