iPhone playing songs NOT on any of my playlists
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.