Have you even if the IP addy's are dynamic (internal) configured your primary and secondary DNS servers at the proxy and firewall?