No VPNs, just my home network with an IP address that rarely changes. What seems to throw it off is when I log in from "conflicting" platforms, particularly iOS + Android. I also have multiple iPhones for work, and it very much dislikes that.
When it gets in this state, nothing will work besides going to g.co/sc on Android--it can't be any other platform, regardless of how long I've had the device--and approving the code request there. If I approve it from any other device, even with a YubiKey, it'll give me a code on g.co/sc, but I'll be told it's invalid and I'll get one of those emails telling me the code was correct but declined due to suspicious activity.
I appreciate the attention to security, but c'mon, it's a YubiKey, and I'm logging in from my usual residential location.