I found the solution! 
So as I specified in another reply, some months ago we enabled Windows Defender Application Control (WDAC) in Audit Mode. You would expect this setting to do just that, audit. It wasn’t after a long time that I discovered the AppDeployToolkit was no longer functioning so I didn’t immediately think of WDAC as a rootcause.
Anyway, I updated the CI Policies XML file before converting it to a policy, like this:
added:
<Rule>
<Option>Disabled:Script Enforcement</Option>
</Rule>
From MS: This option disables script enforcement options. Unsigned PowerShell scripts and interactive PowerShell are no longer restricted to Constrained Language Mode. NOTE: This option is supported on 1709, 1803, and 1809 builds with the 2019 10C LCU or higher, as well as on devices with the Windows 10 May 2019 Update (1903) and higher. Using it on pre-1903 versions of Windows 10 without the 10C or later LCU is not supported and may have unintended results.
removed:
<Rule>
<Option>Enabled:Dynamic Code Security</Option>
</Rule>
From MS: Enables policy enforcement for .NET applications and dynamically-loaded libraries. NOTE: This option is only supported on Windows 10, version 1803, and above.
I will probably test a little further if maybe I can get away with only adding the first part, or only removing the second part. I might also do some testing with signing the script and not do any of the above steps. But anyway, I’m happy I finally found the root-cause and I hope this post can help someone in the future!
Two things bother me:
- this should not happen in Audit Mode
- setting the GPO to disabled, deleting the policy file from the computer and restarting it, did not fix my problem. From MS: https://docs.microsoft.com/en-us/windows/security/threat-protection/windows-defender-application-control/disable-windows-defender-application-control-policies
Best Regards, Ronny.