They probably doing it from country where it's legal. In most countries there is no law that would be applicable in this case.

Which countries is it legal in?

They aren't, or at least, they won't be if Google decides it doesn't like them anymore and decides to bring the matter to court.

The CFAA says it's a crime to exceed "authorized access". Authorized access is whatever the server's owner says it is. If they change their mind, you must cease and desist or risk both civil and criminal penalties. A contract defining the length and nature of your authorization from the server's owner would go a long way to establishing your rights to access, but no one is going to give that to a small player.

You forgot to add: In USA.

Unfortunately this is true in almost all of the developed world. While developing countries may not have specific legal prohibitions, we know that that doesn't stop big companies from having their way. Heck, even a first-world country like Sweden couldn't resist the pressure from Hollywood to prosecute and jail the operators of the Pirate Bay, which had long been recognized as totally legal in Sweden.

Another issue is that on the internet, jurisdiction is a very messy affair. An American judge will likely determine that California and/or the federal government has jurisdiction over such a case because Google is based in California. Most developed countries have treaties with one another that allow them to enforce foreign civil judgments on behalf of the jurisdiction that entered them. Most developed countries also have mutual extradition treaties. The countries that don't can easily be paid off by an interested party.

Isn't Google search based off of Google "scraping" the web?

Bingo