I don't use spotify, but my media keys are working great everywhere I've tried. I'm also the guy that fixed the media key support for the stock firmware on github.
It works for me on linux, on windows in media player/foobar2000/etc... and even works in youtube if it's focused.
Are you sure you set up the keys correctly? You know in the firmware there's three tables.
1) the key/data table
2) the onPress function table
3) the onRelease function table
Media keys and normal typing keys use DIFFERENT press/release functions, if you changed the data only and not those functions this would explain your problem.
I'm betting the keys that are "working" for you were already media keys, and the ones that aren't working were normal typing keys you were converting over, but never updated the function tables.
Let me know if that guess is right.