Actually the issue isn't attached by the Ubuntu version, but the desktop environment. The media keys does not works in Unity desktop (Ubuntu 16.04 default), but works in others desktops, like Gnome shell(Ubuntu 18.04 default). For example, if you install gnome session in Ubuntu 16.04, the keys will works perfectly
Don't think media keys depend on name order. From my experience, it really only controls the app that started first. A quick fix is to start Spotify after you boot and leave it there. Media keys will always work for Spotify in this case. As you have mentioned, this isn't something the Spotify app can do to remediate.
Excellent tip about looking-up the DBus mpris registry entries. I usually have the opposite problem. If I have both Spotify and Clementine running (I use Clementine for certain radio stations not available in Spotify) Spotify responds to the media buttons but not Clementine. If I close Spotify then Clementine responds to the media buttons.
I was inspired to build on your DBus command, this will yield the process ID as well as the DBus name. This will make it easier to pin-point the culprit using your process viewer.
DBus Media Player & PID
for qualifiedName in `dbus-send --session --dest=org.freedesktop.DBus --type=method_call --print-reply /org/freedesktop/DBus org.freedesktop.DBus.ListNames | sed -n 's/.*"\(org\.mpris\..*\)"/\1/p'`
printf "$qualifiedName\t"; dbus-send --session --print-reply --dest=org.freedesktop.DBus / org.freedesktop.DBus.GetConnectionUnixProcessID string:$qualifiedName | sed -n 's/^[[:space:]]*uint32 \([0-9]*\)$/\1/p'
In your case i would suggest to try my mpris-control app then. https://github.com/BlackDex/mpris-control/ . You can then create specific global hotkeys via your desktop tools, gnome, kde etc.. an handle that. I have super+<media-keys> linked to spotify and nothing else. And without super is just normal behavior.