Comment: The solution exists, use it (Score 2) 204
The ability to deny service to a blacklisted device already is part of the GSM standard and the central registry needed to get this working:
http://www.gsma.com/technicalprojects/fraud-security/imei-database
Now it is only a matter of getting the carriers to actually use this list to deny service. In most SGSN, all it takes is changing a config flag.
Yes, that hard!