Their logic is that they have claimed complete ownership of a sound, even if you bought a cd or a digital copy of said song. It would be like walking into a dance club, telling the dj to stop, and demanding that everyone buy the song and then going home. I could post of a video of me at race track where they played some lady gaga song over the intercom and some company flags my video because they intercom decided to play a song in the background. It's stupid. You might as well shut down every radio station, every dance club, and stop making music.
Radio stations and DJs pay to be able to do that. If someone is selling a service where they play songs and they do not have license to do that, then they could be shut down.
I think the issue lies in the fact that you can't purchase or be granted license for audio that takes place in your videos, at least not that I know of. You would think that Google or the streamer would be able to provide some sort of royalty deal to the owner of the audio.