Resumidamente, sería (en mi opinión) rootearlo, reiniciar en modo CWM (Custom Recovery) Hacerle los 3 Wipe's (Data, cache y Dalvik Cache) y ponerle la ROM Oficial de Samsung por Odin.
De esta forma tendrías el movil 100 % limpio y con una ROM oficial de Samsung, sin porquería de Vodafone, Movistar etc..., no haría falta formatear la SD externa, pero si te quedas mas tranquilo, guarda tus fotos, videos etc.. y la formateas antes.
Si me he equivocado en algo, que alguien me corrija.. para hacer todo esto, mirate los tutoriales que hay en este foro en la parte superior con "chincheta" ;)
http://www.htcmania.com/showthread.php?t=405776