Welke verdere regels heb je er in zitten en wat zijn de default policies? Dit kun je zien dmv "iptables -vnL". Met de genoemde regel heb je de OUTPUT geregeld, maar wat heb je aan de INPUT zijde gedaan? Het verkeer moet namelijk ook vanaf de mailserver terug kunnen komen.
Probeer dit eens in combinatie met je eerdere regel:
iptables -A INPUT -m state --state RELATED,ESTABLISHED -j ACCEPT
iptables -A INPUT -p udp --dport 53 -j ACCEPT
iptables -A INPUT -j LOG --log-prefix "ipt-input: "
Werkt het dan wel, dan moet je het dus in de INPUT hoek gaan zoeken. Werkt het niet, dan kun je in /var/log/messages (er vanuitgaande dat je iptables logging daar naartoe gaat) wat er wordt tegengehouden.