This happens to me all the time. I usually log out of all of my accounts on each of the devices, and then log back in. Sometimes if you delete too many songs the other devices need a little time to catch up.
I am sorry you've been having so much trouble. Are you deleting the songs while you are offline? If so, the online version usually takes precedence over the offline version, which could explain why they keep showing up.
Any update? I have a song in my library that keeps on coming back after I delete it. I tried logging out on all devices but it just keeps on adding it self the second you delete it online. Song is "In my Head" by Queens of the Stone Age