Removing the entry "HKCU\Software\Microsoft\Windows\CurrentVersion\Explorer\UserSignedIn" under [IncludeIndividualRegistryValues] in the Default Apps and FTA DEM profile was the solution for us. Not only for New Teams but also for the Security App.
if the UserSignedIn has the value "1", appx / msix apps don't get registerd for the user.
Hope it helps
Regards,
Tom