Can you use an IP address that you might have used before? Maybe they are seeing a new IP address and that tipped the scale in their fraud prevention algorithm.
I access the Internet using the browser's incognito mode. So Google considers each login as from a new device.
That or petition at their offices.