Parece que o VPS ao qual você está se conectando é (ou foi no passado) usado para fazer muitas consultas e o Google não gosta disso. Você provavelmente precisará alterar o endereço IP que você está conectando também. [Eu usei um proxy SOCKS exatamente como você descreve para não apenas fazer pesquisas no Google, mas também comprar coisas]. A solução é provavelmente encontrar outro endereço IP / VPN para usar.
Você também pode querer ver o navegador que está usando - o Google pode não gostar da string Referer -, mas suspeito que esse não seja o problema.