The device may synch with other accounts (fb, skype, whatsapp.....) and if you delete the contact from your phone contacts, when the device synchs, it puts it back again... You could stop the synch process or delete the contact from all your social media....