My process above still works, but it simply gets around a race condition issue, where Windows Update (yes, oddly enough) is in charge of wiping out "staged packages."
According to Microsoft, the "other fix" - and I still consider this issue to be a bug - is:
Cause of the problem:
Windows Update (WU) downloads newer versions of packages you have and
“stages” them as Local System, so that when you go to the store to
update the apps, the update process is as quick as possible. WU will
eventually clean up the staged packages that were never installed.
What are some consequences of having "Staged" packages?
Staged packages prevent you from installing that particular package in development mode
Staged packages eat up some disk space, but due to hardlinking, the effect of this is mitigated. If a file is identical between multiple
versions of a package, appx deployment hardlinks the files instead of
maintaining two separate copies of the same file.
How do I find the "Staged" packages?
In an administrator powershell prompt, the command:
get-appxpackage -all
will display all packages on the machine. For a staged package, the
PackageUserInformation will show {S-1-5-18 [Unknown user]: Staged}
2. Using powershell filtering, to get the list of all staged packagefullnames, you could do:
get-appxpackage -all |% {if ($_.packageuserinformation.installstate -eq "Staged"){$_.packagefullname}}
How do I get rid of the "Staged" packages?
Download psexec
from sysinternals tools, written by Mark Russinovich
To get rid of all of them, run in a regular admin/elevated command prompt (not powershell):
psexec -s powershell -c "get-appxpackage | remove-appxpackage"