Buenas tardes @DiouS.

Los únicos que pueden bloquear el IMEI, obtener su ubicación y detección del celular, son los mismos operadores móviles. Existen software de PC especializados en formatear celulares móviles bloqueados, solo con un cable USB; en otros casos se utiliza el "modo Recovery" con las combinaciones de botones físicos, pero por lo que tengo entendido esta técnica solo funciona para dispositivos anteriores.
Y bueno, lo demás ya te lo imaginas, crean una nueva cuenta de google, nuevos datos y fin de la historia. Como está hoy en día Argentina, con la delincuencia a tope  dudo mucho que la policía se gaste el tiempo en localizar un celular robado cuando tienen casos más importantes, no te lo digo de mala manera, solo que así es la policía en varios países, sobre todo en Latinoamérica.

Lo ideal es contar con una aplicación de rastreo, en iphone ya tiene una incorporada creo (no uso iphone) y al instante es cuando tienes que localizarlo ya que luego lo formatean y no queda mucho por hacer. Siguiendo con el IMEI, he oído casos donde lo cambian por otro y para eso hacen uso del modo "root", si en tu caso fue así, seguramente lo mandaron a un técnico o bien, son rastrillos y lo vendieron por 100 pesos para la droga.

Dirígete a cualquier casa de Samsung y pedí más detalles, espero tengas suerte.


Edit: Decile a esos policías de mi parte que le pregunten a la NSA cómo hacen para seguir los pasos y capturar a personas importantes a través del IMEI del celular, las mejores herramientas las tienen ellos.