I have some good news. As Fritz let me remote into his computer I made a small (not risky, I hope you don't mind) experiment and installed Intel's OpenCL runtime on his computer and voilá. Now the denoiser is working using both CPU and GPU.
So, it looks like neither AMD nor Nvidia are including OpenCL runtimes in their drivers, but Intel ones can do the job.
This is what I installed to make it work: https://drive.google.com/open?id=1-tdxS ... OzLj50nWD4
I'll add this to the documentation at the Denoiser page.
I hope this helps. Thank you Fritz for letting me test this on your machine!