I got it working!!
We were trying to use the wrong HEX all the time.
Instead of
Arduino-COMBINED-dfu-usbserial-atmega16u2-Uno-Rev3.hex I had to use
Arduino-usbserial-atmega16u2-Uno-Rev3.hex from here :
https://github.com/arduino/Arduino/blob/master/hardware/arduino/firmwares/arduino-usbserial/Arduino-usbserial-atmega16u2-Uno-Rev3.hexmd5 ba4b38e08f625cacfbeb3fb4a70d5567
The first sign that got my attention was that this HEX was also 12228 bytes like the HID hex file. They appeared to be identical (at least size-wise).
Although the Flip software is a bit odd and doesn't always upload the hex although it seems to succeed (checked what was uploaded by saving the FLASH as a new file) I finally pulled it off.
Windows greeted me with a new device and after installing the UNO drivers I just successfully uploaded the Blink sketch

Amazing how much relief a blinking led can create.
Big thanks to Nick and Coding Badly for your support!