I knew from past experience that Windows registers UE-V settings template location via a scheduled task which enables UE-V to synchronize application settings between client computers. In this case, the fact that stood out was that the scheduled task did not run properly on systems on which the problem had occurred. Normally, the task would execute a PowerShell script which will then proceed to enumerate the Inbox UE-V Templates and register those and then disable the scheduled task (as it needs to run only once on a machine). Following a brief investigation, we determined that the task runs through only if the logged-on user has administrative permissions (which in an Enterprise environment usually spells trouble as it significantly increases the risk of lateral escalation (Pass-the-Hash (PtH))).

Now that the problem was understood, we needed a way to work around the issue. I was aware of two possible workarounds:

1. Run the C:\ProgramData\Microsoft\UEV\Scripts\RegisterInboxTemplates.ps1 script during OS deployment.
2. Configure the "Settings template catalog path" group policy setting (it controls the "Template Auto Update" scheduled task which is configured to run as SYSTEM.)

This led me to the recommendation to deploy the second workaround as it would fix the issue for the existing install base. The customer configured the "Settings template catalog path" group policy setting to point to "C:\ProgramData\Microsoft\UEV\InboxTemplates" and selected the checkbox to replace the default Microsoft templates that are installed with the UE-V service, verified the suggestion and confirmed that the issue was solved.

I believe that this issue is fixed in Windows 10, version 19H2. However, I did not have time or need to verify this (yet).