They do @winston11
If you call back half the time it will be the number that is unassigned or even with no service (like 6476471234 this one is not up for grabs as I understand)
It's just game of chance if you do or don't get hit today
Just an FYI... It is trivial for anyone using commodity VoIP providers or business phone systems to arbitrarily send any number & name they want as the outgoing caller ID... I've seen it myself. It's the same reason Google hangouts dialer is able to make calls show with your own caller ID...
Also, because of that never use the option in your voicemail to skip having to enter a PIN if "calling from your own number"... someone forging your number in outgoing caller ID can sail right in.
In this day and age, I would not trust any one phoning you if your unsure who it is. These people will try phish any information out of you. Like you said they were saying that the phone number was stolen, would services Canada be calling you? Red flags should be going up. Just be very careful what personal info you give over the phone. If its legit, usually these people already have that info, so why would they ask for it..
This has been happening to me too. I changed my voicemail to let people know a scammer is using my phone number without my permission and that it's not actually me calling them. I wasn't going to change my phone number.