Wow, it both surprises me but also makes me feel justified in that I keep telling people to make backups of things they care about including something like a Spotify account (if your song lists are dear to them, at least the titles and other metadata that they could rebuild from) and other "cloud" or SaaS services. Anything one cares about, back it up! (Not to you but as a PSA)

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?