Parece-me que denyhosts está verificando um arquivo para suas listas de hosts sendo negadas (/etc/hosts.deny talvez?), mas escrevendo hosts recém-negados para /etc/hosts.deniedssh; já que eles não são os mesmos, nunca "percebe" que eles já foram adicionados, então eles continuam a adicioná-los novamente.
Como você conseguiu gravar em /etc/hosts.deniedssh?