Your own private VPS isn't too bad. I use that with a firefox with privacy settings turned up to eleven and don't have problems with google (yandex on the other hand always serves me captchas)

But on any anonymous VPN shared with other people google captcha bans IPs pretty quickly