La memoria interna sólo se debe formatear mediante el flasheo de un archivo .pit (generalmente conocido como latona) que es específico de cada teléfono y en ocasiones también difiere entre firmwares, aunque no siempre.
Ese archivo .pit formatea la memoria interna y prepara las diferentes particiones para que a continuación puedan flashearse las distintas partes del firmware.
Nunca se debe formatear desde el PC, a no ser que sea un usuario avanzado, utilices el Android SDK Tools y GParted, y sepas muy muy muy bien qué es lo que estás haciendo.
Si después de flashear el latona (marcando en Odin la casilla re-partition y flasheando el archivo .pit) y posteriormente flashear el firmware que quieras (KPE por ejemplo) tu movil sigue con las aplicaciones, con el fondo de pantalla y con los ajustes que tenías antes de hacerlo, entonces tienes 99,9% seguro un problema hardware de memoria interna.