These contacts are most probably stored not only in iCloud, but also on your device separately, in the device-only contact group called "on my iPhone".
Your situation is probably a remnant of the times when you synced the contacts via iTunes. Then they got migrated to iCloud and were effectively doubled, but you only saw one contact in the Contacts app, because your iPhone (or iPad) displayed only one entry when contacts were doubled like that.
What you need to do is go to the Contacts app, touch "groups" and turn off the iCloud group(s), but leave the group "on my iPhone". Then you will be able to ultimately delete the contacts that were there.