Some of the networks I work with do the "everything behind NAT" thing and get bitten by this. Using a pool of addresses helps but... This is only going to get more painful with more people doing >"Carrier Grade" NAT...
I Run CGN with tens of thousands of broadband users being translated behind /24 pools and experience no issues with Google whatsoever. (APNIC ran out of IP's some time ago) Occasionally there are issues with things like banks and universities firewall rules who get confused when hundreds of users are accessing them from one or two IP addresses, but this is not often. The biggest issue is the DDOS attacks have a much bigger effect if the upstream's block our destination IP before we can take the target out of the NAT pool. But that is an education thing primarily. Blocking ddestination IP's for DDOS mitigation is going to have to be phased out, its really just laziness and it rewards the attacker.