En teoría haciendo un reset de fábrica al teléfono deberías dejarlo completamente limpio, ya que se eliminan todas las apps instaladas.
Revisa las apps instaladas en la Google Play Store por si hay alguna sospechosa que se volvió a instalar cuando cambiaste físicamente de teléfono