すでに解決したかもしれませんが，一応自分が理解していることを．．．
# すみません．忙しかったのでニュースをチェックしてませんでした．

> iptables -A INPUT -m state --state ESTABLISHE,RELATED -j ACCEPT

御存じの通り，TCP/IPは最初にコネクションを張ります．一方iptablesは，
パケットに対して，書かれた順番にルールを一致するまで検索していくので，
最初の(SYN)パケットには多少時間かかります(ルール位置に依存)．二番目
以後のパケットは，ESTABLISHEDの状態ですので，上のルール(が先頭に
置かれるから)によってすぐACEEPTされ処理が終了します．これはパフォー
マンス高いというわけです．

> ちなみに、iptablesで、INPUTのポリシーをDROPにすると、なぜかDNSの名前解決
> が出来ないんですけど、やっぱり
> iptables -A INPUT -m state --state ESTABLISHE,RELATED -j ACCEPT
> が必要なんでしょうか？（泣）

使えるようにするのがもっとも理想的ですが，それでもルールをちょっと修正
する必要があるでしょう．具体的には……↓

> ACCEPT tcp -- anywhere  hogehoge tcp dpt:domain
> ACCEPT udp -- anywhere  hogehoge udp dpt:domain

この二つのルールを削除して，代わりに下記のルール
iptables -A INPUT -m udp -p udp --sport 53 -j ACCEPT
を追加してみて下さい．ポイントは，dportではなく，sportです．
# DNSサーバから返って来た応答は，sportは53で，dportは一般に
# 53ではありません．また，tcp 53は使われていないようです．