TDMA and CDMA phones register in the network through a process known as authentication. Since in the HLR, the cell phone number exists in the system database with reference to a particular ESN, rather than a SIM card, each time the phone calls out it has to reauthenticate with the network, to make sure that nobody is trying to spoof the network by programming a different phone with the same number.
Authentication involves something called, funnily enough, an Authentication Key, or A-Key for short. This key is, in short, the result of an algorithm involving the serial number of the phone and a number of other factors. It helps keep you from getting loads of charges from Tijuana and places south on your bill.
Periodically, customers will call in who for some reason have lost that authentication. Maybe they traveled in the wrong place, or the network burped, or they were just screwing around with their phone. In any case, they can no longer call out, and incoming calls are going directly to their voicemail box.
Reprogramming a TDMA or CDMA phone helps more often than you might think, but won't necessarily force the issue enough. One solution is to attempt a hard power shock, which basically amounts to taking the battery off of the phone while the phone is still on.
More common, however, in addition to the short programming, is a Dummy ESN Change.
This amounts to going into the billing system (usually) and changing the ESN, which is an 11 digit serial number (or 8 if the customer's phone serial number is in hexidecimal) to the same number, but with half the digits as 0's or 1's.
So, for instance, we have a customer with a nokia phone whose serial number is 06404335221.
We change the serial number to 06404000000, and save.
Once the change has processed through the system and been updated on the switch, we change it back. Then we reprogram the sucker.
Seventy-five percent of the time, this fixes the customer's phone. Occasionally, rarely, we will actually program a new A-Key into the phone, but this harms more often than it helps, opening the phone up to wider security issues.
Beyond that, we generally try to talk the customer into upgrading to GSM, because TDMA is a piece of crap anyway.