While I don't completely rule-out the possibility of finding a technical solution, if such a solution exists it is going to be really hard to find. Re-associating "anonymized" tokens is a lot easier than it looks in many situations, and it doesn't take much data leakage to JOIN tables together. I would love to be wrong on this topic. It would be absolutely incredible if someone can invent a way to make mobile devices still work without leaking any information that can be tracked.
I totally agree with separating authentication from authorization; we need to do that anywhere it is possible, not just for mobile devices. Unfortunately, the trend has been in the reverse direction. :/
I would have thought the problem in mobile networks might be easier than elsewhere. Where the wireless network is public infrastructure, for example, if devices used randomized MACs then I'd imagine it'd make them much harder to track.
You'd still need to authenticate with a VOIP provider. But by breaking out these services I would guess it would make tracking much harder.
I totally agree with separating authentication from authorization; we need to do that anywhere it is possible, not just for mobile devices. Unfortunately, the trend has been in the reverse direction. :/