Ответ найден господа!
Fail2ban по умолчанию при отправке команды reboot чистит все таблицы банов. Зачем правда, не понятно.
Логи со временем снятия банов совпали до секунды, с временем действий юзера рута, который отправлял сервер в ребут.
Так что ничего криминального :)
