Fail2ban удаляет только свои правила и цепочки из iptables. Другие он не трогает. Вы случайно не добавляете свои правила в цепочки самого fail2ban'а?
Также проверьте, что у вас включено сохранение правил при перезапуске iptables:
/etc/sysconfig/iptables.config
IPTABLES_SAVE_ON_RESTART="yes"