How to permanently delete text substitutions?
I have experienced this myself since OS X 10.10.1 and since iOS 8.1.x. I think it is an iCloud syncing bug. Old deleted entries return. Duplicates get created. I haven't attempted to, but I believe the only solution is to contact Apple support. Or wait for it to hopefully resolve itself.