Still, it's weird that Google doesn't accept a recovery code. Then again, I had a similar issue where I had nothing set up but a recovery email address and password (back when 2FA was rare), and after confirming both, Google said "well, we still think it's suspicious, why don't you use a device where you're already logged in" (my account had no active sessions that I knew of, besides that I was traveling). Luckily I didn't need it for anything as I had my email moved away already at that time. I still can't access that account today and I switched to throwaway accounts for things like youtube comments or app downloads from the play store (need to download that government authentication software somehow...)
Did Google specifically reject the recovery code as invalid, or did it accept all entries and then their algorithm rejected the login outright?