It accepted the backup code and my correct password and then wanted to verify more stuff, which there was nothing, and just said "Sorry, we can't give you access to your account right now".
Had I followed Googles own advice and relied entirely on these codes (which I thought I was doing) I would still be locked out of all those accounts, purchase history, Google Play Developer, etc.