One of the workarounds for the current DNS problems is that servers introduce source port randomization. So it’s time for you to patch your DNS server so it uses random source ports. If for some reason you are unable to do that, iptables can help. Michael Rash has a good write up of how that works here.
In Vuurmuur there is now a per rule option, that can be enabled for the SNAT, MASQ, PORTFW, DNAT and BOUNCE actions, called ‘random’. This passes the ‘–random’ option to the iptables rules Vuurmuur creates. Note that you need a recent distro for this. Debian Etch is too old, Ubuntu Hardy is fine. The new functionality is just released in Vuurmuur 0.5.74 alpha 6. Check it out!
*UPDATE 29/07/08* it turns out iptables/netfilter does not undo existing randomization so removed the text suggesting that.