Lo más probable es que estos contactos estén almacenados no sólo en iCloud, sino también en tu dispositivo por separado, en el grupo de contactos exclusivo del dispositivo llamado "en mi iPhone".
Probablemente tu situación sea un remanente de los tiempos en que sincronizabas los contactos a través de iTunes. Entonces se migraban a iCloud y se duplicaban, pero solo veías un contacto en la aplicación Contactos, porque tu iPhone (o iPad) solo mostraba una entrada cuando los contactos se duplicaban así.
Lo que tienes que hacer es ir a la aplicación Contactos, tocar "grupos" y desactivar los grupos de iCloud, pero dejar el grupo "en mi iPhone". Entonces usted será capaz de eliminar en última instancia, los contactos que estaban allí.