Firewall DNS issues

I am working on setting up a Firewall solution for a client. Basically - to get outside the network we have to point DNS to the firewall - not to the ISP's DNS server. So the reality is I am having slow DNS look ups to get outside the network. So it appears that the main bottle neck of the firewall is DNS. Does anyone have any ideas for how to get the clients the ability to look outside the server for DNS? Thanks!!!