Knee-jerkery against the old rule: If you don't need the info, don't keep it.
Ever get prank-called by the police? Alright, so they wanted someone who gave them my number though I am not him. And after a couple calls and patient explanations I'm in the wrong city and have owned this number for more than a decade, they did stop calling, mostly. I'd rather fob them off on the phone repeatedly than having them lift my number's records and kick in my door at oh-dark-thirty to accuse me of using a false name, either to them or to the phone company. Anyhow.
"such crimes going unpunished is a price worth paying for a little anonymity"
Actually, I think that such crimes going unpunished is a sign the police aren't competent, not up to the demands of policing in these times. They're *supposed* to be able to find perps without expecting the perp dropping a convenient ID card first, thanks. And the phone company knows too well already where each currently switched-on phone with a sim of theirs is, thanks.
So officers will just have to be quick and trace the phone before the call finishes. Modern technology can do that, or at least be made to do that. Now for an efficient police apparatus that can send the nearest PC plod to the last known location within minutes, instead of weeks, at least for sufficiently important cases. The longer the wait, the colder the trail gets. So get on with it already.
They also ought not need massive databases of everything happening. All they should need is access to the data as it comes in "live", and pick out the bits and bobs they actually need right this moment. They're there to solve crimes, not collect data that might give insight later in crimes that might conceivably have been committed, possibly. A little realism here, some practicality, some feet on the ground and PCs plod in the streets, please.
The purpose if the police is to keep a lid on crimes and find the perps that did it. Even if we actually could, "pre-crime" would itself be a grave violation of our fundamental freedoms, as that includes --as I've argued before*-- the freedom to err. Thoug that in turn does not imply getting excused from the consequences.
I'm not willing to give up anonymity because the police can't be arsed to organise themselves beyond their nineteenth century modus operandi. With progressing information and communication technology, they ought to be more respectful of my privacy, not less.
Thus, governments have no business demanding ID where it isn't really warranted by some direct and obvious need.
* http://forums.theregister.co.uk/post/784312