One reason I found out causing this are "staged" packages. This happens, if the same app package is installed by another user account or installed from Visual Studio but reset from Windows App Settings.
How-I-fixed-It:
1. Get psexec tool from https://docs.microsoft.com/en-us/sysinternals/downloads/psexec
2. Run psexec -s powershell -c "get-appxpackage | remove-appxpackage" within a admin commandline box
I found the information here:
https://stackoverflow.com/questions/13865930/how-to-uninstall-an-app-that-another-user-installed
