I'll look for the books for a citation for it later, i believe it's Neo-anarchists guide that first refrences it, but in short, Docwagon does do a substantial (though not a majority by any means) part of it's business model in selling services to the sinless particularly . Likewise most of the corporations of the world arn't interested in owning sinless, there's just no money in it. Easier to just offer them a corporate sin for working 80 hours for company store credits or selling sinless stuff out of the stuffer shack.
Basically you've decided that for whatever magical reason the gang or shadowrunners are going to find one fake sin out of thousands of them, and orders of magnitude more real ones. Their goin gto find that and track it. My counter point to you is in your theoretical "walls have ears" world driving people around in a car would never be enough to throw people off the scent, if every street gang and shadowrunner has CIA level information sifting and gathering technology effectively moving anonymously is impossible. Likewise I think you are confusing two things a dedicated enemy can and will put time and effort into finding things out about people via the streets. Calling people, paying bribes, and canvasing the pavement. But that's a long way from a gang leader getting a call about every illegal purchase some member of his gang makes "Hey Joe, i just thought i'd let you know, Billy came in here the other day and bought a level 2 fake ID, a streetline special, and a pack of smokes. Did you authorize that?"
Information is for sale but part of selling information is knowing who it's valuable and what it's worth. In order for the gang to know that Joe the ganger checked into the hotel or the clinic someone would have to see Joe checking in and know that that's joe the gang member and that his gang is looking for him. "Using his contacts" isn't some magic fix for finding a non notorious/noteworthy person.
For me at least the presumed limitation on a persons ability to hide is resources and talent. A gang member is going to know or at least suspect he knows what it would take to hide from his old gang, how their going to look and who their going to go through. Likewise if he's got money and ability to reach out to a fixer and get shadowrunners hired he's got some level of resources.
Again we come down to you've got a problem that you came on here looking for a fix but you don't want to use the tools provided because they don't fit your picture of how the world works. If in your world the walls have ears strong enough to pick up Joe ganger checking into a no tell motel under an assumed name but no one would notice a stolen vehicle driving around the city for 72 hours then that's not the sort of problem anyone else is going to be equipped to fix for you. We can throw suggestions and see what sticks but some of our basic suppositions on how the world works are going to be wrong, and some of the tried and true methods for controlling action (principal wanting to exercise authority) arn't going to work because you have decided they won't.
My honest advice to you is next time you put together a job for your players first come up with the job, then throw in some complications that the PC's will have to work around, because life is seldom ideal. Maybe their bodyguard target needs see his kid one last time, maybe the object their stealing is a fish tank full of fish. If you give your players no constraints on what they can do then you have to be prepared for more and more easy fixes. But there are reasons why things are never so simple. In this case again you just need to decide why this particular gang would be able to find