He podido comprobar con un terminal que cuando me empieza a ocurrir esto el /data/data esta al 100%, por lo que es posible que efectivamente sea por eso.
Pero lo que no he hallado aún es una solución más allá de lo que comentáis: backup, wipe y vuelta a empezar.
