It depends on the context. In googles case they are most likely checking ports to see if the box is a proxy, completely legal. Much different than scanning Fort Mead's ip address space(cookie for anyone that can tell why thats bad without needing wikipedia ) looking for vuln servers.
Port scanning is an example of the difference between law and policy. Most ISP have service policies that say no port scanning. I do not know of a single LAW making port scans illegal. Even under the most draconian legal interpretations still require intent unless they can prove damages caused by negligence(difference between scanning one server, and why you cant exactly scan the entire ipv4 address space, though people do it anyways).
Well I have logs where (what is most likely) google touched ports on boxes which are non of their business.
I looked it up and you ppl are right, it is not illegal perse, ISP's can indeed have a policy against it.
What I came across are posts where individuals where dragged to court for scanning boxes.
The scanning by itself was not illegal but they led the court to believe it was because they wanted to break it, judge being clueless about computers and networking....
Seens to boil down to individuals can be screwed.
I can recommend watching Fedor's(creator of NMAP) talk called "scanning the internet" , quite an interesting one.
Aaaaand back on topic, sorry for the derail.