I remember that the dutch police some years ago already used so called "sms-bombs" to contact mobile phone subscribers that were around a crime scene months before.
It is simply inherent in the technology. You wear a mobile phone? (not even smart) So you are traceable with all consequences.
The solution? In any case not technical in nature. We will see.
Two years ago when he told me this I thought he is a tinfoil-hat paranoid person but now I know he is right.
But if you hang out just a little bit with pot heads in eastern Europe you know the best solution is to turn off your phone and take the battery out when you don't want people tracing you or lightening to your conversations.
Put your cell phone in flight mode and use it exclusively as a PDA/music player/etc.
Let people contact you on a landline and email - more than enough.
I know its true of phones that are "off" without the battery removed - stands to reason it applies in flight mode too.
Since the power button is a 'soft' switch, controlled by the phones operating system, it's possible that a phone can be compromised so that even if it appears to be 'off' it is actually still powered up and listening to the cell network, but this is in no way a 'standard' feature. The same attack vector/vulnerability is present for flight mode, a compromised phone can lie and report that the radio is off when malicious software is using it.
Removing the battery is a mechanism to preclude any possibility of your phone being exploited, and may be appropriate depending on your risk tolerance and/or threat model.
if you have a tinfoil lined bag (like a thermo lunchbag), it's even easier than removing the battery.
If you're doing something illegal, or talking to someone about something illegal, leave your phone at home, and use your $15 dumbphone with an unregistered throwaway sim.
Just switching SIM cards may change what account info you're using, while still providing plenty of information for determined investigators to use.
The solution can be political, too, and it would certainly help, but I think it's a lot less sustainable from government to government.