In Australia it's outright common to have recycled numbers. I've had a few. My work phone had to be given a new number 3 times in the first 6 months until I had a useable one, because I kept getting random calls at all hours of the day/night looking for people who weren't me. It's mostly for work phones for some reason (I assume they have a higher rotation of useage as employees come and go, and nearly all companies use the same provider, Telstra), but my brother got a number that was someone else's before him too so it does happen privately.

The idea of phone numbers being the prime authenticator is laughable. I'll actively avoid any service who ever does this.