When I decide I no longer like one or more songs from my iTunes library I remove it in iTunes (and not just the download).
they then disappear out of my iTunes library and computer. All as expected
Then i go to my iPhone and Often i will still find some of these removed songs on my phone.
Not all but some songs never disappear slowly filling up my iPhone. this happens to songs that had been downloaded to the iphone but also to songs that remained in the cloud while they are long gone from my computer and iTunes.
(I use iOS 9.3.1 on an iphone 5 64gb and iTunes 126.96.36.199 on win 10 64bit)