Music deleted on iPhone will not stay deleted

Hi everyone,

I have been searching on and off for a couple of years about this issue and I have not yet come across a solution. I have always manually managed my music library and ever since the ability to swipe to delete music out of the music app came out (iOS 6?) I have had trouble with it.

Essentially, I will swipe to delete music as I go through my library on my phone and come across something I no longer like. As soon as I sync my phone to my computer (windows laptop) the songs I have deleted reappear. This also affects my fiance who has a macbook pro so it isn't a windows issue.

Some background on the devices that have been involved.

iPhone 4S - issue has occurred from iOS6 through to iOS8 - I always keep the iOS up to date.

iPhone 5S - Always up to date

I have had this issue on my old laptop (Win 7) and my current laptop (Win 7 then Win 8, then 8.1)

This has occurred on fresh set ups and restored set ups of my iPhones.

My fiance has has this issue on her iPhone 4 and 5S and as mentioned earlier she has a macbook pro. We both keep iTunes up to date so it is not an issue with old iTunes software.

Again, we both manually manage our music so it should not be syncing any music from iTunes. It deletes fine if we delete from iTunes, just not from the iPhone. Also, neither of us use iCloud or iTunes Match and I have turned AutoFill off.

Any help would be really appreciated as this has been driving me mental for a couple of years and it isn't practical to plug my phone into my laptop every time I wish to delete a song.