Three weeks ago, I had a phone stolen straight out of my backpack (In front of a whole bus-stop full of observers facing me who saw ''nothing''!)
SO, I did everything correctly from then on:

*do the ''find my device'' - CHECK!

* Got google to wipe old phone on reboot - CHECK!

*Get phone service provider to block old SIM - CHECK!

*Get new SIM with same number - CHECK!

* Got new phone, inserted new SIM - CHECK!

* Started Google setup process on new phone- CHECK!

*Completed Google setup process on new phone - IMPOSSIBLE

Everything I try to do? Google RIGHT FROM THE START insists on sending verification codes to old phone. With absolutely nothing I can do about it to remedy (Access to google account is fine via laptop. No one has tried to hack it etc). Using a trusted device doesn't matter (I am always signed in via Win10 laptop, via exactly same router. Same routuer in fact old phone was, and new phone is signed in through) SO ''trusted'' device method is bull-S for mel'.

'Recovery email'' route is a farce. It only tells me if I have logged in, in a manner google thinks is unusual (It never had been, ever! It has only ever been me from elsewhere).

Strangely too, in a section in my google account settings (via laptop browser) in 'Persional info''> phone number, a section says (Just wait till you read THIS!):
''This phone number has been added to your Google Account
0044 [my phone number]
Verified • 1 Jan 1970    '' 

VERIFIED JAN 1970?   HOW SO? My phone is a time traveller?

IN short my new £150 Galaxy a15 cannot be set up and used due to verifications going to the old stolen and auto-reset phone. With absolutely no route to rectify, and an unaccountable Google.

Means I cannot get into eBay etc, due to their also sending codes to my new phone (Which I will be receiving IF I ever get into my new phone. And I have a overdue item which hasn't arrived which I need to contact seller about, for instance)
And worried about not getting health appointments and various work stuff done.

Apparently I may have made ''too many attempts'' to set up my phone???