The solution would then be to make all phone records public to avoid the black market issue, and I know that my parents wouldn't find anything wrong with that.
Because they can't imagine a world where people skip phones when they do crime, or
In such a world, not having a phone on you will be viewed with suspicion. When this fact is brought up in the court, it will be often enough to sway the jury to convict the accused.
you assume law enforcement won't become too reliant on phone records to find you in the first place.
You mean like a phone book? (which still is a thing where I live)