Does your firewall also allow egress tcp sessions on port 53?
Can you run tcpdump while trying to resolve? And what address(es) specifically fail for you?