A mi me paso lo mismo, los borraba desde el movil y nada, desde el pc y nada. Y ademas al encender el móvil tardaba media hora en salir el teclado para introducir el pin y se quedaba vibrando como para indicar un código de error vibraba una vez y luego vibraba 2 veces muy seguidas.
Creo que tengo la sd interna jodida por grabar vídeos con la cámara. Por ahí había un hilo donde decían de probar la sd interna para ver si te había salido defectuosa haciendo eso precisamente, grabar mucho video.
Lo solucione activandole el modo download y recovery que no lo tenia y haciendo el factory reset y wipe desde el modo recovery.
A partir de entonces no he vuelto a tener problemas aunque tampoco he vuelto a intentar borrar nada.