The problem keep persist! Editing the contacts on one device do not take effect of editing the data on the cloud, I think? Even if the contacts are edited on one of the devices the time when sync them on anther device the error is copied too! If I leave only one copy on one of the devices, and delete the contact list of the rest it may help, but I didn't try cos all contacts may get lost. What do you think. Thank you for the opinion!
Using iCloud for Contacts (and/or Calendar and EMAIL) the "MASTER COPY" is on www.icloud.com. You may have Contacts on the device that is NOT part of iCloud.
For your Contacts go to https://www.icloud.com/#contacts. Make sure that your contacts are complete and correctly setup. This is extremely important.
Assuming they are perfect on the iCloud.com then delete them from the device by going in iCloud Setup and uncheck Contacts (like on the iPhone or iPad) and it will ask if you want to delete the contacts from the device and you say yes. Then you turn back on the Contacts and it will "reload" that device. You do this for every device.
AGAIN, DO NOT DELETE Contacts individually. Go to Settings / iCoud and Turn Off Contacts. You will get a prompt, select "Delete from My iPhone". Then if you go into the Contacts App they should be NO Contacts.