I would also consider that the problem is the client you are using to connect with the VPN. Sometimes the VPN provider's client are just borky and Google is the first to figure out the issue. I just recently encountered this.

P.S. 95% of search attempts can be adequately satisfied with DGG. I'd suggest you isolate G products to a specific browser, this way you isolate what data you actually provide G with.