I had the same issue in May, and now (since 3 days), coming out again.
I also try everything what you write. Nothing working.
In May I resolved by reset windows. I was not very happy to do this, but it works.
This week appears the same situation again. App icons are away, the app seems not to be installed but, if I try to install it, it simply doesn't work. In the Microsoft Store download area, show me that I've got to download the new version, but it doesn't work too.
It seems to me a issue that appears every time 343 send a new update / patch over the Microsoft Store.
24/6/2020 was one.
I resolved now in this way (not fine, but it works)..
- Login a second user in Windows, give him Administrator policy.
- With this user I delete my main Windows user. In this way I'm 100% sure that all the %appdata% are away.
- Create the main Windows user account as new, give him administrator policy.
- Login in windows my "new" Main user, login in Microsoft Store.
- Now I can reinstall MCC..
It seems to me, that by update of MCC, the Store set the app as "uninstalled" even if is not uninstalled, that's why the Store self try to install MCC again, but cannot do this.
By the way, I think the solution "reinstall gaming services" https://www.halowaypoint.com/en-us/forums/85d779d52cfd46918b4f8b638f2e3c7b/topics/mcc-won-t-install-from-microsoft-store-pc/40366514-67a6-4b5d-b5fe-65580c3029b8/posts?page=2#post34 could be also good, because the gaming services are used also to check if you can use the game or not.
Next time, that the issue come out again, I will try it at first.
Thank you all.