I think it's more a matter of that the phone was in a particular cell than that the call was made.
I would like to see cell-tracking technology whereby a phone never reports its ID when idle and pinging tower. I'd like to see the tower push three bloom filters on ping, one of all predicted to be in the cell, one of all predicted to be in the area (surrounding cells), and one of all in the system.
For a flat assumption of 10^12 phone numbers CC-AAA-RRR-XXXX including country codes, assume nearly 100% of all numbers are being dialed at the exact same time. You can gain a 1% probability of error on if a number is being dialed in about 116GB. In any situation of over 50% saturation, you'd invert: list what numbers aren't being dialed, hence the size of the worldwide packet is 58GB. That's the theoretical bound in an insane situation. (Besides, you can only dial half the phones in the world at once...)
In reality, we don't have 100 country codes, and not all countries have 10 digit phone numbers. In America, there are only really 800 possible area codes, 269 in service in the USA, and 26 in Canada. Not all areas saturate the exchange; most exchanges aren't saturated. The number of phone numbers world-wide isn't 142 times the size of the number of people.
So let's assume 10 billion numbers instead, not all of which are cell phones. You're looking at 580MB for the packet to express near 50% saturation of numbers being dialed *right now* for the whole world. That's much better.
Phones ring for approximately 10 seconds. They're answered or taken to voice mail by then. In addition, most phones aren't being dialed at any given time. If we assume 1 in 7000 cell phones is currently ringing, the worldwide packet is 174kB for a 1% margin of error.
So let's call the regional a 10 million phone coverage area, and the local a 1 million phone coverage area. Assuming 1 in 7000 phones is currently ringing, the packet sizes are 174kB worldwide, 178 bytes regional, and 17.8 bytes local, for a 1% margin of error. That is: you have a 1 in 100 chance of the phone deciding it's probably in the bloom filter when it's not. If we double the sizes here, then the false positive rate is 0.01%, or 1 in 10,000--almost never.
We can further reduce these by scaling them dynamically, and by delaying the ring if you're out of known area. I'll use the double-size numbers for a 0.01% false positive chance.
Let's say somebody calls your phone. The cell system predicts, based on prior data (i.e. you're usually in this city, your home address on file is here, whatever), that you're in the 1 million person coverage area contained by some cells. In Baltimore City, we have 660,000 people; 1 million coverage is bigger than my city. So the system adds you only to the 35.6 byte local dialing filter for a 1 second cycle.
If your phone fails to respond to the tower, the system leaves your number in the 36 byte local dialing filter. It begins including it in the regional dialing area. The regional dialing area excludes any phone dialed for less than 1 second, any phone found in a local dialing area, or any phone included in the local dialing area filter. More than 95% of phones should be excluded: there's better than a 95% chance that you're currently in your local area. The filter is about 89 bytes on average, assuming 1 in 7000 phones in the 5,000,000 phone region is ringing.
The worldwide filter is different. If in 1 more second you don't answer, the cell system adds you to the bloom list for the whole world. Assuming a 95% chance of someone being in the region if not in the local area, that's 95% of 5%, or 0.25%. Assuming 10 billion phones, the worldwide list of numbers currently being dialed is 9 bytes.
For a 1 in 10,000 false positive rate, you'd have to push 134 bytes of dialing filters. If you're outside of your normal region, there's a 2 second delay. We can further step this with a 100 million phone region to net whole countries in the last list, but we'd introduce a 3 second delay for people who are outside their country.
In this system, no phone would tell the tower its identity until it wanted service. Of course, most phones are sucking down data, so this is all pointless; but, if you shut data off and are on straight receiving calls, your phone doesn't actually tell the towers where you are--it doesn't identify itself. The towers say, "Here is a bloom filter of phone numbers. If your number hits the bloom filter, it's 99.99% likely you're being dialed right now." If you're in any of the three filters, you ping the tower and tell it you're ready to answer, and in this cell.
You're ready to receive calls, and yet the tower doesn't know where you are unless someone calls you.