aiuto...
intanto cerca iptabled4dummies, ovvero come configurare un firewall guida in italiano che non guasta mai.
Poi: se reindirizzi le chiamate alla porta web, pop3 e smtp al tuo proxy, per quale motivo non dovrebbero andare piu' le chiamate al DNS? Deduco che la configurazione di iptables non e' congruente con quanto dici. Ricorda che con iptables ovviamente puoi mascherare e nattare anche le chiamate dns. Alternativamente installa un server dns che faccia banalmente da cache sul tuo server, cosa che velocizzerà di qualche punto percentuale le ricerche dei nomi. Prova a postare qualche stralcio, magari commentato a dovere, delle regole iptables...