- You have a list of suspects, tap those. And those around them, And maybe those around them. A heck of a lot less intrusive than taping the planet.
- Pay the telecom people to store the data, and only get the data with a court order. This is similar to how the armed forces pay the airlines to have planes capable of being used by the military in a surge role, but normally run by the airlines.
- Establish an outside entity. Outside entity will take real phone numbers and give back a unique hash. Telephone companies will send meta data to NSA, but will substitute these hash values for all telephone numbers. On court order, the outside entity will say "john terrorist has has 3141592". NSA will then do the proper searches, and say "we need the user for hash 12345, the outside firm will say its King Roland (spaceballs)". In this way, no single entity is able to abuse the system. They could collude, but it sets the bar higher.
Now, will any of these solve the problem? No. Will it make everyone happy? No. Like always, security, like liberty. is a compromise.