True story: I bought a new car with Android Auto. On the way home from work, I told it, “Play Put it There by Paul McCartney”. Spotify did not play the song. Instead it, played some (sort of) random Paul McCartney songs with some Kanye West intermingled. (I’m not joking about Kanye). I tried the same thing at home with my Cortana Invoke speaker. It played the correct song.
Both Android Auto and Contana used Spotify but for whatever reason, the Cortana played the right song.