Cara, vc usa Autenticação Local ou por AD?
Se for por AD, esquece, eu tive que colocar o Avast que tem a configuração de Proxy dentro dele.
Se for Local, vc libera os seguintes sites:
.nfe.sefazvirtual.rs.gov.br
.cpid.bradesco.com.br
.caixa.gov.br
.caixa.gov.br
.fpdownload.adobe.com
.fpdownload.macromedia.com
.java.com
.sun.com
.verisign.com
.mscrl.microsoft.com
.crl.microsoft.com
.microsoft.com
.watson.microsoft.com
.content.windows.microsoft.com
.genuine.microsoft.com
.c.microsoft.com
.windowsupdate.com
.download.windowsupdate.com
.update.microsoft.com
.mpa.one.microsoft.com
.stats.update.microsoft.com
.crl.microsoft.com
.au.download.windowsupdate.com
.urs.microsoft.com
.mscrl.microsoft.com
.sqm.microsoft.com
Tem outros ai, é que essa é minha lista pronta que uso para proxy com autenticação local.
Se for pelo AD até atualiza, mas tem que liberar a porta 80, ai ja viu, se o usuário tirar o proxy do navegador ele vai fazer a festa.
Qualquer coisa acompanha os logs do Squid com o comado tail -f /var/log/squid/access.log
Manda o MSE atualizar e verifica com esse comando os DENIED.
Tenta ai e posta os resultados, abraço!!!