The first time this happened I completely lost all access to my Google account. I transferred all of my important email correspondence over to a Microsoft account and I have never looked back. Unfortunately I still need to maintain another Google account for my phone (Android) to work properly, so there are times I still get bitten by it. It's absolutely infuriating when you get a new phone and specifically need to log in with your Google account to be able to do anything, that's exactly the time Google blocks you from being able to get into your account, because it's apparently detected the new phone and decided you're a hacker.
This also happens to me regularly with PayPal, almost always when I am traveling overseas, at exactly the moments that I really need PayPal to work so I can pay for something related to my travel. It's so annoying. Tech support never, ever solve the problem. All you can do is wait and try again later until magically it works. Sometimes weeks later.
The only thing I can say for certain is to never try log into your account over open wifi or over a VPN connection, because somehow Google (and PayPal) seem to flag that as a hack attempt no matter how many times you correctly confirm your identity. And once you've been flagged once, your account gets caught in some kind of loop where even after you get back onto an apparently blessed IP address, you're still locked out for some unspecified period.