Digo por decir...
Desconocía que se pudiese cambiar el IMEI por software, pero en este caso, yo lo que haría sería ponerle el IMEI de alguno de esos telefonos que todos tenemos por ahí tirados con un par de añitos y que se dejaron de usar por actualizar de terminal. Por ejemplo si bloqueasen mi IMEI de mi SGS yo usaría el IMEI de un Nokia 5110 que guardo como reliquia por ser mi primer movil.