I was having the same problem. I found that lifting the HDMI cable slightly resolved the issue.
In my case, the weight of the cable caused the mini-HDMI connection to bend down. Supporting it so it is just above horizontal caused the monitor/TV to detect the connection.
I hope this helps.
P.S. My nuc worked for a few hours without needing to lift the HDMI cable.