>To my knowledge, a radio station or music streaming service doesn't have to negotiate with the record label to play a given song, they just have to pay a small royalty as defined by law.

The copyright holders can legally prevent their recordings from being streamed by Spotify. Famous examples were Taylor Swift and Neil Young withholding their music from Spotify.

For extra nuance, copyright holders can't stop cover songs from appearing on Spotify. So the Taylor Swift cover songs do have to pay compulsory license fees to her and her record label.

Swift withheld from Apple Music because they were giving it away for free and not paying her (or anyone); I don't recall it being kept off spotify?