You will not believe it, but it turned out to be excess thermal paste that got under the black sticker around the processor and video card. I accidentally stumbled upon one of them, that due to excess thermal paste, HDMI can not work well. I decided to check, it looks like on the Mac under the sticker there was a thick layer of terpop paste mixed with glue and dust. I cleaned everything and the problem went away.