Ubuntu – How to get HDMI sound to work in 16.04

I recently upgraded from an ancient Ubuntu installation to 16.04 LTS. Everything works well except for one thing. I can't get HDMI sound to work.

Some notes and observations:

1. The computer itself is an Intel NUC
2. The installation is completely standard
3. The only sound and video output is through the same HDMI plug to a TV
4. The sound section in System Settings shows the "HDMI/DisplayPort – Built-in Audio" device as expected, and all volumes are at 100% and nothing is muted
5. Likewise for pavucontrol, it lists the "Digital Stereo (HDMI) Output" profile under Configuration and the "HDMI/DisplayPort (plugged in)" device under Output Devices, and all volumes are at 100% and nothing is muted and the sound level meters show there is sound being generated
6. However regardless what sound / pavucontrol say, there is no HDMI output
7. But in Kodi, while if I select the "Default, Default Output Device (PULSEAUDIO)" audio output device in Kodi there is no sound, if I select "Built-in Audio Digital Stereo (HDMI), HDMI / DisplayPort (PULSEAUDIO)" HDMI sound works just fine in Kodi. (I suspect this is because somehow Kodi with this setting outputs straight to HDMI and not to default Pulseaudio)
8. Outside of Kodi, if I bring up alsamixer, hit F6, select HDMI, and hit m and m again (mute and unmute) HDMI sound comes back, but as soon as the sound source stops (like a pause a youtube video) there is no HMDI sound again
9. Using aplay I can output test sound through HDMI completely fine (using the correct card and device)
10. I also tried installing Fedora 24, but still no HDMI sound

I have tried pretty much all sound issue fixes I have found, but so far the sound issue persists:

1. Update Intel drivers
2. Update Ubuntu (besides 16.04 I also tried the 16.10 beta, but same story there)
3. Setting the default pcm card and device (from testing with aplay) in .asoundrc
4. Setting the alsa sink device with load-module module-alsa-sink device=hw:X,Y in /etc/pulse/default.pa

Here's the output from alsa_info.sh, pactl list sinks, pacmd list-sink-inputs for reference.

What can I do to debug and fix the issue?

EDIT: I also posted this question on 01.org.

I later ran pulseaudio with higher logging verbosity. You can find the log here

Here's what I did:

1. I started the daemon
2. I tried increasing and decreasing the volume. I expect the little pop sound everytime i change the volume, but there is no sound.
3. I then start spotify and start playing a song, but still no sound
4. I then open alsamixer, select the HDMI card, and I mute and unmute the sound
5. Now there is all of a sudden sound
6. I increase and decrease the volume again, but this time there is sound
7. I then pause the song in spotify and wait for a while
8. When i start playing the song again there is no sound again
9. I kill the daemon

I am using HDMI card 0 device 3.

I am not plugging in any other sound cables.