Office 2016 kann nicht installiert werden

I pulled my hair out for about 12 hours before I resorted to using procmon to see what the heck was causing the issue. I tracked it down to a registry key:

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\AppModel

Right before the install fails, it checks this key, which my other machine didn't have at all. It seems to be something related to apps installed through the store (this had 365 which was uninstalled previously). I simply renamed the key and the install worked fine.

Things that didn't work:

1. sfc /scannow
2. DISM repair
3. .net repair tool (didn't really do much and found no errors)
4. Office removal tool (said it wasn't installed)
5. Rebooting
6. cleaning temp folders