Desde el teléfono solo se borran los datos y se vuelve a los ajustes de fábrica, no se borra la caché. También se puede borrar desde los ajustes del sistema la caché temporal de las apps, pero no la del sistema.
Desde el recovery, como ya has visto, también te da la opción de borrar la caché del sistema eliminando cualquier rastro de la instalación anterior y dejando el teléfono a 0, limpio como cuando se compra.
Mejor desde el recovery claro.