Were you scraping with real browsers or something like Mechanize/Curl? Rate limiting at all? Proxies or real servers?
We didn't rate limit, we would just increase the size of the cookie pool if a captcha was hit, which was rare because we would scrape n-pages till a threshold was met to prevent that session from being captcha'ed so we wouldn't have to captcha solve it. We had two pools, the primary pool and the "chilling" pool, cookies near their captcha life would cool off for a few hours before returning to the active pool which behaves just like any other resource pool, every page scraped would "borrow" a cookie out of the pool, customize the encrypted location key, and make the request with a common user agent string.
Scaling it was difficult but once we had it figured out, Erlang was invaluable to us and our dependence on IPs dropped once we figured out the cookie methodology.
Solving captchas is cheaper than renting IPs.
Parsing it wasn't hard but it wasn't fun...
It was highly effective and very scalable because you can stimulate the captcha pages easily and out-of-band generate a very large cookie pool by captcha solving. Then when you go to actually scrape google you can balance your pool of IPs and cookies, chilling them before they trigger another captcha, to handle spiking demand. Contant, sustained demand was very easy to plan for.
Anyway, we stopped using the API after the third day and realized it was not only not accurate and you couldn't turn many knobs (want to scrape results as they look for a different geographical region?)