I don't think the cloud syncing is the issue at all. I'm having a similar problem with my S4. Specifically:
Since roughly Dec 10, I can no longer permanently add or delete files on my SD card. Files, whether photos or other documents, will appear to be saved or erased. However, as soon as the phone is powered off or rebooted, anything that was copied or saved to the SD card disappears, and any files that were deleted reappear. I have erased several hundred megs of junk only to have it *instantly* reappear when the phone is restarted, far too fast for it to be downloaded back from some cloud or something. It's like the file system on the SD card is stuck on Dec 10... I know on most PC OS's delete files by simply changing the first char of their filename to NULL, or something along those lines. So the data in the files don't actually get erased till the disk gets defragged or it's overwritten. Also, the new data must be getting copied because I can look at pictures after I take them. But then the phone gets restarted and the file names or pointers to where the data is on the disk or whatever get reset to how they were on that day for some reason. Everything that was erased is back; everything new is gone. I have tried using the phone as a USB storage device on both Mac and Windows and erasing the files from laptops, but that has the exact same effect.
This has broken Evernote which means I basically can't use my phone for work stuff any more.
I'm not sure but I put off upgrading to lollipop until around then. don't know if it's related. doubt it.
It's super frustrating and I would very much like just to smash my S4 with a hammer, but I can't afford a new phone at the moment.
Any insight would be appreciated.