[Barracuda]

Нихрена не понял... Причём тут файрвол до машин с установленным, в качестве ДНС-сервера, ДНС-сервером провайдера...
На роутере строите ДНС сервер, у которого, в качестве форвардера (есть такая фича полезная), стоит сервер провайера. В чём прелесть фичи - читайте матчасть. У меня именно так всё и работает. В качестве основного сервера ДНС на клиентах прописан наш сервер (он же роутер). Если (сервер) он не знает чей-то адрес, то он лезет в инет сам, а не клиент этим занимается... А клиенту вообще надо  отрубить выход по днс-запросам в инет - ибо нефиг лишний (хоть и копеечный) траффик генерить...
этого, чтобы не быть голословным, попробуйте по внешнему имени кого-нит пингануть (тот же yandex.ru - почему-то истрически сложилось так, что первым пингую его при проверке работы ДНС) и послушайте траффик при этом (на роутере, ессно). Если болт, то займитесь настройкой ДНС-сервера... Ну а если пингуется копайте глубже... То, что сквид резольвит имена - это далеко не факт корректной работы ДНС и, тем более, не факт корректной настройки сети в целом.