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.hex
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!