Lo más probable es que estos contactos se almacenen no solo en iCloud, sino también en su dispositivo por separado, en el grupo de contactos solo para dispositivos llamado "en mi iPhone".
Su situación es probablemente un remanente de las ocasiones en que sincronizó los contactos a través de iTunes. Luego se migraron a iCloud y se duplicaron de manera efectiva, pero solo vio un contacto en la aplicación Contactos, porque su iPhone (o iPad) solo mostraba una entrada cuando los contactos se duplicaban de esa manera.
Lo que debes hacer es ir a la aplicación Contactos, tocar "grupos" y desactivar el (los) grupo (s) de iCloud, pero dejar el grupo "en mi iPhone". Luego podrás eliminar los contactos que estaban allí.