Android no es windows
La unica porquería que te puede quedar de instalar y desinstalar apps son los datos que puedan dejar en la sd, y no vas a formatearla para perder fotos y datos que tengas, ese paso conviene hacerlo manual.
Cuando hayas eso restauracion de fabrica te vas a market, bajas un explorador de qrchivos e instalas titanium, que previamente habras tomado la precaucion de dejar la app en la sd, junto con el activador.
Es una tonteria y una perdida de tiempo no usar titanium para restaurar apps con sus datos (perderías historial de watsaap, etc), porque manualmente estarías dos dias para dejarlo como estaba, y con el titanium 10 minutos.

Mi procedimiento seria el siguiente:

1º - Backup con el titanium.
2º - Copia el contenido entero de la sd en el pc
3º - usa backup to gmail para asegurarte de que realmente se guarda en tu gmail todo el historial de llamadas, contactos etc. Luego vuelve a usarlo para restaurarlos al movil.
4º - Restauracion de fabrica con formateo de memorias (excepto la sd)
5º - borrar manualmente de la sd los directorios y archivos que creas que pertenecen a apps que ya desinstalaste.
6º - ve al market, baja un explorador de archivos (mala costumbre de los cocineros de no incluirlo en la rom), e instala el titanium.
7º - Restauracion de escritorio, cuentas, apps, etc con el titanium
Listo