Bueno según la teoría si, pero hay casos que dejan rastros, carpetas con ajustes etc
Como pasa por ejemplo oxk Windows, desinstalar un programa y muchas veces vas a el directorio en pc y por magia sigue ahí alguna carpeta con nombre del programa, no está el programa en si, pero si restos, aquí en android igual, si se desinstala, pero muchas veces quedan cosas que afectan a futuras reinstalaciones, no tienen por qué ser malas, pero tampoco pueden por que ser buenas ;)
Sabes borrar datos de una app?
Si no te hago un pequeño video y te explico