Why is your internal DNS server sending the packets to the internal firewall IP? Looks like there is no rule active that allows this traffic so it hits "deny all". Not sure why it is still working when you disabled it, but please do not disable the "deny all" rule.
Did you check on internal and external interface by using tcpdump if the delay is caused by the firewall?
Here some links to the service portal that may help:
Thanks for your reply. My mistake, I didn't reconfigure the forwarders on my DNS servers, so they were still pointing to the old gateway address, which is now the firewall's address.
That seemed to fix the DNS resolution slowness.