I think what happens is this:
Your phone (when you buy/activate it) registers you on what is called a HLR - Home Locator Register (I think). All your details are stored there. The chances are it won't be anywhere near your home, but it's kinda random. When you switch your phone on, it connects to the nearest mast and your details are 'sent' from the HLR to your VLR (Variable Locator Register) - the place you want to use the phone. This is why, when you turn on your phone after it's been off for a long period of time, it can take a while to connect to a network. This is because your details have to be re-sent from your HLR.
So, therefore, the networks know roughly where you are so don't need to send to everywhere!