Eso sólo pasa en Windows. En sistemas Linux (Android) no hay registro ni merma de rendimiento. Además, al desinstalar una app tienes la opción de eliminar los datos asociados. A mayores lo que puedes hacer es eliminar la carpeta que haya podido crear la app en la SD interna (sobre todo apps que permiten descargar ficheros de internet).
Enviado desde mi GT-I9000