As you've isolated the problem to be specifically between your phone and those headphones, the only thing I can think of at this point is if there's some kind of build-up right up at the base of the headphone's plug end (see jpg)
View attachment 122381
A headphone jack is essentially just a mechanical, spring loaded switch, with metal contacts that must aligned exactly with the metal contacts on the headphone plug, enabling the audio signal to go to either the internal phone speaker or the headphone. If there's something like an old bit of tape or something right where the plastic and metal meet, it might be just thick enough that it's preventing the plug from being fully inserted into the jack (which will prevent the jack's spring loaded switch from being pushed outward). Kind of a long shot, considering those headphones do work elsewhere but as almost everything in a smartphone is miniaturized that often applies to tolerances too.