If at all possible, consider using a NAT pool instead of translating all outbound web traffic to a single IP address. When I ran Tribune's network (with about 15K internal client IPs), we were blacklisted by Google several times due to high query volumes. In the end I built a pair of /24 NAT pools, so for example all internal 10.x.y.124 addresses are translated to "kevin.nat.trb.com".
In my experience, Google does temporary blacklisting based both on rate and also for certain types of queries; you can reduce your chance of a ban by using a smart proxy to rate-limit or deny certain types of query, or to choose the source address based on the URL requested, basically have a "low risk" and a "high risk" source address.
