An update to this issue. Hopefully useful for someone in the future who encounters this.
As the symptoms in the first post include the drive not spinning up at all, I suspected an issue with the power to the disk.
Disconnected the disk, removed the SATA and SATA power cables from the NUC. Then I connected a regular desktop SATA cable from the NUC motherboard to the Toshiba disk, and setup a separate ATX power supply next to the NUC. I used the ATX to power the disk drive using a SATA power connector. Fired up the NUC, and sure enough the disk is recognized in the BIOS and fully functional.
Next step was to reinstall everything in the NUC (so the factory SATA and SATA power cables) and turn the NUC on, to measure the voltages on the SATA power connector to rule out a faulty cable. I measured the small PCB that connects to the disk at the power connector and the PCB does receive the proper +5V and +3.3V (red and orange wires).
At this point I could have probed further to see where the problem lies, because some connections on the small PCB look suspicious to say the least. However this has already cost me 2 evenings and by now I am certain it is a HW defect that was already present when I purchased the unit, it just has gone unnoticed so far. I will be sending the NUC back for warranty, but I would not be surprised to see more NUC's with similar defects.