I am not from Intel but similar reports are fairly common here. A few things you might consider trying are: connect to a different input on your TV, for example the TV's manual may detail that input #1 is the one intended for computers (the reason is that the NUC is probably trying to request information from the TV about resolution details). And consider trying a different graphics driver version (search carefully in Intel's Download Center and/or community messages), because some versions of the graphic driver may do a better or worse job. Also realize that there is often also an audio driver involved with HDMI, so consider taking care to note whether that driver version (typically called something like Display Audio) is a factor in the compatibility. Finally, you mention different cables but if you are always using the same mini-HDMI adapter then maybe see if you can obtain/try something else such as a min-HDMI to HDMI *cable* (not adapter). I am not saying that any particular item is the problem, but those are factors which often seem to be involved in compatibility - I realize that I have not addressed the AVR (which is often another factor).
The Intel NUC has to decide whether it wants to output on DisplayPort or HDMI at some point (defaulting to DisplayPort). Presumably this has to happen at a very early stage (when booting). It seems that when there's no "connection" on HDMI during boot, HDMI is being completly ignored from there on.
I'm wondering whether this problem is present on the NUC5CPYH and NUC5PPYH. Those devices have an HDMI and VGA port. I'm assuming it's defaulting to HDMI then. If the TV is only "available" after the startup routine, then it at least gives the TV another chance to identify itself.
After buying a new cable everything seems to work fine.
Except loosing sounds sometimes when turning off tv/reciever and can't use both USB's in the back at the same time.