¿Debo eliminar las cuentas antes de encriptar y restablecer de fábrica?

No veo que sea necesario eliminar ninguna cuenta (Paso 1) siguiendo los pasos que has indicado en tus comentarios. Sin embargo, si estás usando Android 5.1.1+, es probable que quieras evitar Protección contra el restablecimiento de fábrica . En ese caso, sólo es necesario eliminar la cuenta principal de Google vinculada al dispositivo. (He añadido paréntesis alrededor de dos de sus pasos que creo que son innecesarios) :

1. (Eliminar cuentas) Sólo tienes que eliminar la cuenta principal de Google vinculada al dispositivo si éste está en Android 5.1.1+
2. (Encrypt) Este es el valor por defecto en Android 6+
3. Restablecimiento de fábrica
4. Instalar y utilizar la trituradora de datos
5. (luego encriptar y restablecer de fábrica de nuevo)

Los tokens de la cuenta se encriptan en el paso 2 y, por lo tanto, resultan confusos para cualquier actor malintencionado que intente recuperar su información.
Al sobrescribir el espacio libre en el paso 4, la clave de cifrado maestra original puede sobrescribirse (y cualquier espacio que no sea "espacio libre" ya fue sobrescrito por el restablecimiento de fábrica). Android puede almacenar la clave en un área a la que no llegue una aplicación de borrado que sobrescriba el espacio libre; sin embargo, el espacio libre que originalmente contenía los datos cifrados es sobrescrito por el borrador y, por lo tanto, incluso un mal actor que tenga acceso a la clave maestra no podrá descifrar nada. Por lo tanto, cualquier cifrado/reinicio posterior más allá de los pasos 2 y 3 originales no tiene sentido.

_{Actualizada la respuesta con el comentario de Robert más abajo... y por segunda vez.}