[bystander]

Ну, даже не знаю... Засада какая-то. На первый взгляд, конфиг нормальный - за исключением выше обруганых never_direct и always_direct, которые просто ни к селу, ни к городу. Имхо тут что-то еще. В store.log что на тех запросах, которые не должны пройти? Точно нормальные (2xx-3xx) коды? Просто у меня такое впечатление, что на самом деле NAT в сетке работает. Они убеждаются, что их squid не пускает (откуда и записи в логах), отключают его и прут напрямую, без squid'а.
Вот такая гипотеза.