Really? I'd imagine you'd need two codes (one for the login, one for access to your 2FA settings), but not being able to recover at all using them seems horrible!

It just gives some error like "this login method is not allowed for this action" or similar.

Interesting. I can't confirm though - I personally changed my 2FA device 2 weeks ago using a backup code. I couldn't find old yubikey that I used as 2FA for google, decided to regain access with a backup code and add my new yubikey, and it worked flawlessly. It probably helped that I used the same machine as always. Google does a lot of undocumented heuristics in the background, and you either get additional verification or not.

Yes, same machine helped, it's definitely one of the factors it uses.

I have a near-20-year Google account I can't access because I lost the 2FA number. I have the username, password and recovery email. But that isn't enough, apparently.