I just had a similar problem occur on my S10, bought new headphones but they had the same issue.
Turned out that I had two music apps running - the first app was playing music when the headphones were plugged in and I think the headphones were trying to control the second app, but the first app had control of the sound so nothing happened. This might explain it working briefly after a restart, the second app not having quite started up completely.
This issue is solved. If the solution did not work for you and you want more/new posible solutions, you should create a new thread, not continue this one. I would have locked it if possible.