My experience with changing devices or cities (or god forbid both at once) is that it always requires further authentication, and often fails outright. I have an account which is simply disabled because I didn't set a recovery phone # or email and then changed machines. Everyone I've ever discussed the topic with has described similarly pervasive problems.

Which makes me wonder: what's so different between usage patterns? Obvious Google's auth approach is working for lots of people, so what's distinctive about this block of users who it's constantly failing for?