You don't need to record all phones in the world if you have the metadata of all calls in the world. The NSA or another spy agency could record only calls that match a given pattern: place from which the call originates, who is being called, time of call, previous calls made or received by the line, when the line or phone was purchased, whether this phone's call patterns resemble another phone's call patterns, etc.
They wouldn't achieve 100% coverage, but efficacy would probably be 99%+.
I would guess the problem with this kind of semi-targeted collection is processing power to decide who is a target and schedule the line taps.