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.