Lógicamente si no haces formateos de las memorias (tanto interna como externa) los datos almacenados en ellas permanecerán...
Si quieres hacer una instalación totalmente limpia, haz full wipes (data, cache y dalvik) y full formats (data, cache, system y preload). Formatea las memorias desde el recovery (format emmc, format sdcard) y pasa un limpiador de script+limpiador de kernel y te quedará el móvil más limpio que una patena.
Al formatear las memorias no te dejará nada en ellas, por eso, si te bajas una rom en formato .zip y te la pasas a la memoria interna (p.ej) al hacer el formateo te la cargarás y no tendrás la posibilidad de flashear nada.
En este caso es mejor ir a "Mounts and storage" darla a montar USB, conectar el móvil al PC, pasar el .zip y flashear.