Что меняет мой host.deny на ALL?

Мандрайк не видел, но я бы посмотрел в /etc/cron.daily, какой-нибудь скрипт проверяющий/корректирующий security settings

Перемудрил с security level?

TCP Wrappers?

tcp wrappers читают этот файл, но уж никак не пишут в него.

Это у тебя msec хулиганит!!!! Высокий уровень безопастности выставил. сделай chattr +i /etc/host.deny и пускай он обламывается;-))))))))))