Te han machacado los datos de la carpeta EFS (o borrado) y por eso tienes el IMEI genérico, si el tio del SAT te ha dicho que te han cambiado una placa y por eso tienes otro IMEI es que no tiene ni puta idea.
Posiblemente el del "servicio técnico de la ciudad" te ha metido un firmware con el Odin marcando la pestañita de generar de nuevo el EFS.
Prueba con lo que se dice en este hilo:
http://www.htcmania.com/showthread.php?t=174891
El que lo creo ha resuelto el problema con los consejos que le dan ahí.
Yo por si acaso lo primero que hice nada mas comprarme el móvil fue hacer una copia de seguridad de la carpeta EFS.
Si no consigues restaurar el EFS tendrás que reclamarle a MoviStar, aunque lo mas probable es que te digan que has cambiado el firmware y por eso se te ha borrado la carpeta EFS, sea como sea tendrán que enviarlo a Samsung.
EDIT: Acabo de leerme el hilo que te he puesto y creo que eso no vale para tu caso...