I had the same issue and I figured it out not sure if it works for all but what I did is I switched the clocks on the lock screen and found one that worked so when you swipe on the clock to get to your music or if its already there from the lock screen it should work. Try switching clock types from lock screen
I tried switching clock on the lock screen don't work. Did all that was recommended on this posts and still don't work. Even contacted Samsung and did many troubleshooting and yet still don't work. What I found out is when I use Amazon Music the control media player in the lock screen work. Thus, the Samsung tech support concluded its Spotify issue. I hope for an update soon
I've this problem too with s9+, at first I thought the problem was about my lock screen settings. It still can be about my lock screen permission settings or sth. like that because when I first tried to skip song with my original akg headphone, it said "you cant control with your headphone buttons because its not allowed, you need to change it in settings" or sth. like that.