Deleted Contacts

I noticed that some of my contacts has been missing. But I could see a pop up message every time they change actions (available, busy, change shout out etc.) But when I tried to add them again a message stating that they already exist in my contact list.

Attached is the copy of the said error.