Duplicates not being deleted in Contacts

The method you wrote in your question will work , if you merge duplicate contacts . Suppose there are thousands of duplicates , one can not merge them manually selecting each of them as its a time taking job .

If you are using gmail account a method is there to merge duplicates .

Open webmail by entering gmail address and password , take the cursor on top left and click on drop down arrows of gmail , click on contacts .

A window appears , click on duplicates , if there are many duplicate contacts an option will be there to merge all .

I am not aware what services are you using yahoo , gmail or any ....

Maybe you have contacts from a different account, or maybe you have contacts that are specifically stored in your mac besides contacts from iCloud.

I am not at my mac right now but I believe that you can't merge contacts if they are from different accounts, which makes sense and might explain what you are seeing.

I am having the same issue but with call logs. I was told. When the phone is plugged in to iTunes under summary, where it says contacts at bottom of page check the box and then sync. If you already have your phone setup that way in then uncheck and sync sync.

But the issue is with that setting.

Did you repeat steps 2 and 3?

Contacts – Resolve Duplicates

Contacts (El Capitan): Remove duplicate contacts

You are welcome. If you are willing to use 3rd party software, this may help. I haven't tried it.

Contacts Cleaner

Try quitting and reopening Contacts to see if that will let you look for duplicates again.