A few months ago Google wouldn't even accept backup tokens for me. I was on vacation, and that tripped enough fraud detectors to cause problems. I couldn't log back in till I got on my home network and changed my password.
Eventually I set up my own VPN server so that the services still thought I was using my home IP.