I worked in telecom for years. Last few years I was in the business (about 5 years ago) I worked on a wireless product and some of the software we did was based on CALEA standards. Information on it is on the web. Here are a couple of links, is one is interested. The second one is a specification, so you may want to read it if you are having trouble sleeping. Now there were some at the company I worked at that were considered a gov't team that I had no clue what they did, but I new they existed. Got let go 5 years ago, so don't know about all the changes in the last 5 years.
Like I said I have not been in the business for 5 years. Back then in order to tap someones phone call you had to input into the switch a warrant-id. Also in order to tap someones phone call it took more software resourses, hardware resourses, and had a real time inpact on computer processing power, so I find it hard to believe that they are saying they can collect this data in a network with 100 million tapped subscribers every day. You could tap, voice, data, call event records, but it was costly in terms of resources, and to do it for every subscriber is somewhat difficult to believe. Initially when I was involved the product could support up to 4-5 LEA (law enforcement agencies) that could tap a call at any one time. I can not be certain but I think when I was let go the product could support up to 10 LEA's that could tap your call at any one time. Imagine that up to 10 needed to monitor your call at the same time. In summary in order to specifically tap someones call is expensive in software resources, hardware resources, and computing power, so is this what is actually going on.
When you have a service provider whether it is a wireless, landline, or long distance provider, what is it that you get in the mail each month that you have to write a check for. A billing statment that comes from a billing record. A phone company has to bill you so they have to keep enough data on how to bill you then they send you a billing statement. Now in order to cut a billing record they have to collect data such a originator or the call, terminator of the call, call duration, time of day, calling party number, called party number, etc. Then they calculate what you owe for each call. Now if you dialed an internation number they should be able to get the country code for example and there are tools provide by the equipment makers to search for all sorts of information in the billing record. What I am thinking is that it is not a true tapping of of the call, but my thought is its the billing records that may be given to these agencies. There is quite a bit of information that is collected for the billing record that may not show up on a billing statement. Once again I am out of the field for 5 years. Also when I left they were working on many more busy hour calls due to the processing power of the technology.
I remember working on a product for a long distance carrier many years ago. I think they advertised 400K busy hour calls to 500K busy hour calls as a maximum. Then during the Oklahoma City bombing I heard one of the switches did close to a million busy hour calls. Someone suggested that they must of had to turn billing off to free up the computer processing power, but I have no idea. If one is interested in CALEA check the links below.
Anyhow all of this info is out there.
http://en.wikipedia.org/wiki/Communications_Assistance_for_Law_Enforcement_Act
http://cryptome.org/laes/calea-require.pdf