I thought that I've tried everything mixer wise both forwards and backwards, but maybe I missed something.
Thanks Luke for the research.
I've now tried something simpler: just move the /etc/init/alsa-store.conf away. Do this on your first boot, when sound is still working. This seems to me like it causes the sound to survive a reboot, although sound might be muted (which you can fix either in the sound indicator or with "pactl set-sink-mute @DEFAULT_SINK@ 0").
I know we've had red herrings before, so I'm hesitant to throw a party just yet! So could you others try this as well and see if this makes your audio work?