Happened to me, I was able to get SMS and recovery codes, but Google still required additional verification on now lost phone :D. On the end I acutely found the phone and was able to restore access. So what they do after couple of days of failed attempts the require additional verification, lets call it 3 step.
