I know this may sound silly but have you tried with another HDMI cable? Make sure it fits fine and it is not loose.
Can you also try updating or adding more codecs to the players? Would you kindly provide the dxdiag report and system information report?
How to get it?
Dxdiag Report: Type dxdiag in Start Menu> open> Save> Attach using Advanced Editor Options.
System Information: Click Start> Type System Information> Click File> Export> Save File> Attach using Advanced Editor Options.
After much trial and error I found that the solution to this problem was to force Vsync on in desktop mode, as I expected. The only way to that on a Intel NUC is to enable Windows Aero desktop, which apparently forces Vsync on an application level. More information on why here: How does Windows Aero prevent screen tearing? - Super User
Unfortunately Aero makes videos played in Kodi worse, so I had to force Kodi to disable Aero when running it. But since I don't play videos on two places at once this isn't really an issue.
Strange thing that the Intel HD5000 driver doesn't have an option to force vsync on in all modes(the one under 3D clearly doesn't do anything for desktop mode).