Решение:
Просто. Нужно. Было. Сменить. WIFI.
При подключении к другому роутеру фаервол начал правильно блокировать интернет. Как такое возможно?
Т.е. даже если блокировал вообще весь OUTPUT и FORWARD, то Интернет все равно функционировал. Как будто фаервол вообще не работал. Но, как оказалось, это все происходит только если подключаться к определенному WIFI в определенном кафе. Нигде больше такого я не наблюдал.
Как роутер мог повлиять на работу iptables (правда, что он повлиял именно на работу iptables я уже не уверен)?
Это может быть какой-нибудь глюк network-manager в Debian?