pues la solucion es que te arreglen el imei, al parecer con lo que has intentado si no da resultado es porque tu movil tenia el imei cambiado, de ser asi ese problema no se arregla por ningun medio gratuito solo con setoolbox y ovio te cobraran.
saludos!