Fijaos que gracia, que acabo de tener el mismo problema aqui expuesto, y consegui solucionarlo antes de ver el post.
Ya no solo con el tema de roms que se peten la carpeta EFS y los datos, he notado que si instalas Lockscreens alternativos (todo me ha venido a raiz de la rom MiKi con el lock del sense 3.0) al reiniciar el movil cancelan la peticion de PIN, y por tanto aparece como si no tuvieras IMEI, parando estos procesos o desinstalando estas aplicaciones tambien se soluciona, sin llegar a necesitar de tirar de backups.
Espero que le sirva a alguien, porque a mi me acojono bastante.