O que está acontecendo com a configuração do squid acima é que ele está tentando resolver o DNS público através do seu servidor interno, depois esperando que ele falhe, e então tentando o DNS público.
Eu sugeriria executar um proxy DNS separado no sistema e dizer ao squid para usá-lo. Algo agradável e fácil como dnsmasq permite que você defina diferentes servidores DNS para domínios internos, mas todo o resto vai para o DNS da Internet pública. Parece que o Vyatta inclui o dnsmasq.
Como alternativa, configure o encaminhamento em qualquer servidor DNS interno para permitir que ele resolva os nomes de domínio da Internet e, em seguida, use apenas o servidor DNS no squid.