En mi opinión es normal que no funcione, veamos un ejemplo:
- Un ordenador interno hacer una petición a google.com por ejemplo
puerto 80, llega a tu puerta de enlace con squid que la reenvia gracias
al NAT, como la petición no es para ese host en concreto simplemente la
reenvia y por tanto no va al proxy.
Lamentablemente si no te vale un proxy transparente debido a la
autentificación no conozco otra opción que configurar cada uno de los
clientes. A ver si a alguien se le ocurre algo mejor.
Un saludo.