How about contacting google for advise?
They are the one that forces you to the issue.
They don't like it that you have a 1k clients behind your IP address.
They should tell you what to do.
You can tell them that you are using squid as a forward proxy to
enforce usage acls on users inside the network.
It's not a share to use squid...
It's a shame that you cannot get a reasonable explanation to the
reason you are blocked...
There is only 1 client behind the IP address as it is a test server so
something is going wrong with either routing or requests to google.
Google will not answer any emails.
I suppose one alternative is to use unbound in conjunction with squid
and not redirect any requests to google?