James Halperin's The Truth Machine long ago converted me to the idea that the best way to deal with this is to abandon privacy and the right to privacy as a societal ideal, and hope that our ability to thwart terrorists races their increase in power. Even an opt-in total surveillance system would help a lot by reducing the number of suspects.

I should probably make the case against privacy in a top-level post at some point, but pretty much everything I'll say will be taken from that book. For example, I bet Amanda Knox and Raffaele Sollecito are currently cursing the fact that they don't have a government-timestamped video of themselves at the time of Meredith Kercher's murder.