AWS is an order of magnitude more expensive than owning your own hardware, and Google was leveraging economies of scale to operate much cheaper than people that owned their own hardware (e.g. fault tolerant software vs. "enterprise grade" hardware)
People didn't realize it at the time, but "search" wasn't Google's only core competency. It was also "warehouse scale computing".
Of course Inktomi under Eric Brewer was another search company that realized that search is a perfect application for clusters of commodity x86 hardware, or networks of workstations (which AFAIK came from academic projects like http://now.cs.berkeley.edu/ )
(Don't outsource core functions: http://www.joelonsoftware.com/articles/fog0000000007.html )