Locking down a phone by a carrier would be all but impossible. To many different types out there. It would be a logistical nightmare and expensive to maintain.Blocking network access to stolen phones is an easy, common sense first step. Carriers should also be required to remotely lock down these devices and require ownership verification for future use.
Nobody has any right to use a stolen phone, no matter how they obtained it, and purchasing stolen items is also illegal. The phone carriers have been profiting off of service plans and replacement sales of stolen phones for too long. The carriers must deny service to any stolen device.
Anyone purchasing a used phone should be able to check the database to confirm the phone isn't stolen. An improvement to system would involve a database of IMEI's for verified phones that are for sale. This could provide phone buyers a way to confirm that the original owner is selling the phone, rather than relying on whether the phone has been reported stolen yet.
Ultimately the carriers and police should track and seize these stolen phones whenever possible. The government and phone companies already have the ability to track all smart phones if they need to.
To assume otherwise and believe that this would represent a new threat to your privacy is naive.
If you don't want to be tracked, don't buy a gps phone.
The carriers and police have better things to do than track down a phone.
Simply denying the device access to any network reduces the likelihood of it getting stolen in the first place.
And your phone doesn't have to have GPS capabilities to be tracked.
Carriers can pin you down pretty easy buy tracking tower registrations.