Problemas con las instalaciones y la falta de espacio

Es la tercera vez que me pasa, las dos últimas en mi teléfono actual, un Samsung Galaxy Note 2 con Jelly Bean 4.1.2. Las otras veces solo he podido solucionarlo restaurando el teléfono al estado de fábrica, con el trabajo y la pérdida de tiempo que ello supone y estoy seguro que ha de haber algún modo más fácil de solucionarlo.
Sin nada aparente que lo cause, de la noche a la mañana, algunas aplicaciones dejan de instalarse y actualizarse por falta de espacio de almacenamiento, pero no todas, la mayoría de ellas. No tiene nada que ver el tamaño de la aplicación, pues lo mismo ocurre con aplicaciones de varios MB como con algunas de unos pocos KB, y tanto en aplicaciones nuevas como con actualizaciones. Si desinstalo una que no se actualiza, después ya no se vuelve a instalar por el mismo problema.

Espacio hay de sobra, pues hay 4 GB libres en el almacenamiento interno y 2 GB libres en la tarjeta microSD externa, así que imagino que debe de ser algún problema con una aplicación o servicio del sistema operativo, pero no soy capaz de encontrar el fallo.
El teléfono está rooteado, aunque esto no es motivo para el fallo, pues las dos primeras veces no lo estaba y ocurrió igual.

¿Alguna idea para que no tenga que formatear?

Eso he hecho cada vez pero ya me ha pasado tres veces

¿No hay más ideas?