El SO no tiene nada que ver con las apps, eso sin contar que el hecho de que las apps desinstaladas dejen a veces carpetas sueltas es común a cualquier SO. Si te molestan simplemente bórralas.
Parte de esos 10 mb que te ocupa el Facebook pertenecen a la caché, desde el administrador de aplicaciones puedes eliminarlos. Si eliminas los datos lo normal es que te elimine la cuenta, las configuraciones que tengas guardadas en la aplicación y los vínculos entre contactos FB y agenda. Sería como si volvieses a instalar la app por primera vez, en ningún caso debería eliminarte los contactos de la agenda.
¿Y para qué quieres saber todo lo que hacen las apps? El exceso de información sin los conocimientos necesarios para asimilarla sólo produce pánico (no hay más que ver las pajas mentales que se hace la peña con los permisos). Si lo que quieres es tener perfectamente controlada una app, en el Market tienes apps para monitorización de procesos y gestión de permisos.