Google has always been showing captchas when using their search engine for quiet a long time (even for VPN users). In fact they were even straight blocking users from using that very same captcha: https://bugs.torproject.org/23840
They're identical now, I rarely got the awful one that you're talking about when searching on Google.