I have deleted some songs my roomie used to listen to but they keep playing when I activate music play on iOS 7. I can't figure out how that would happen. A song will come on. I will go to my only playlist. It won't be there but it's still playing. Next week same thing. Makes no sense. Help I hate his music!
Playlists are just organized subsets of your music library, so you might not have the song on the playlist, but still have it in the collection. Even if you just have a single playlist, that doesn't mean that every song on your phone is in it. iTunes will default to the first song alphabetically if you tell it to "Play" when it doesn't have a playlist loaded (i.e. the first time after turning on the phone).
At least under iOS 6 (I haven't upgraded yet), you can see all songs by tapping the "Songs" tab at the bottom of the Music app. If his music is there, you can delete it from there. If it isn't, then there's something else going on.