>Unhoused people tend to get their phones through the "Obamaphone" program, which means that replacing a lost or stolen phone results in a completely new phone number.

Maybe that's part of the issue. Why recycle numbers so aggressively? Give the user a few months to recover their old number if they can prove they are the same person.