The "enforcement" aspect isn't even really necessary - just give out this income often enough and far enough away from the city that traveling back and forth every time is impractical.
I'm imagining SF opening a sizable homeless shelter in LA, busing people down there, and then giving them some sort of BI there. (Yes, such busing has gotten a bad wrap, but bear with the thought experiment). Meanwhile, LA can do the same thing to get rid of their homeless. Each city would be incentivized to spend more, efficiently, on maintaining shelters in each other's cities.
There's a gradient where infrastructure-poor towns in the middle of nowhere would be cheaper. And who would want to move to a majority homeless city to own/work business to serve them? But could this be softened with the return trip being guaranteed, contractually obligated with independent oversight?