The solution is to mandate that the IMEI cannot be changed.. i.e. it is burned into a write once part of the phone. Currently manufacturers are resisting this idea.
Then, all that needs to be done is to have international co-operation on sharing the IMEI blacklist, like is currently done all across western Europe. This is why currently phones need to be sold in eastern European countries like Poland or Hungary... but if the authorities really wanted to solve this problem they could easily get all operators worldwide to share the blacklist...
As others have said, I believe that there is much more to this than theft prevention... more of the government pushing through things they want "for our own good"...