Será 'difícil de combatir' solo porque las compañías de teléfono no hacne mucho por la autenticación de quien intenta el cambio.

Recuerdo que una vez robaron a una amiga su tf. en la playa, al día siguiente la acompañé a la policía a poner la denuncia (ella no quería, porque insistía que no iba a recuperarlo, y esa parte: el 99'999% de las veces será así), pero en la propia compañia es condición indispensable para solicitar otra SIM, presentar el parte de denuncia por robo que emite la policía, luego es un requisito indispensable.

No veo nada complicado, que también se exigiere un parte de la policía en caso de 'pérdida/extravío', pués el mero hecho de tener que acudir a la policía te exige la validación de tu persona, quedando demostrado tus credenciales incluso puede que hasta 'captado' en cámaras en la comisaría y con fecha y hora exactas.

Que luego lo gestiones en una tienda o envíes copia por correo electrónico será otra historia, pero la compañía ya cuenta con una cierto respaldo, incluso facilitando un número de parte que la propia compañía pudiera contrastar con la policía podría saberse si en efecto el papel presentado es legítimo o fue falsificado...

En mi opinión este tipo de 'robo' de datos el culpable es la propia empresa telefónica por un sistema de seguridad a todas luces insuficiente y considero que denunciable, es la propia empresa quien debería asumir ciertos costes y ser condenada a mejorar el sistema.