Android devices get a pass. I'm guessing Google verifies some ID on the phone.
This, btw, is what I think caused me to lose a Google account.
It was an old one I was checking very rarely, someone reset my (strong!) password from a phone. I reset it again, along with the questions, thought I was fine.
They once again reset it and then Google's recovery page was not letting me do anything, apparently I was the suspicious person. Oook Google.
Did you clear cookies before signing in from the other country? As I remember, Google made me re-authenticate via text the last time I cleared cookies, despite connecting from the same IP address as my last login.
Maybe I'm on thin ice..