This absolutely CAN happen without the user deleting the contact.
It is happening to me for the past week (since I first noticed it). Email accounts, etc, are UNCHANGED and iCloud is "on" to back up contacts. I have tried doing the "archive" from a previous date and it did not fix it.
Apple customer service representative basically told me (today during a call) the contacts do not just disappear without being deleted. She was certainly not convinced that I am not deleting them. In fact, she eluded to this by showing me very simple ways to delete a contact as if I must be doing this on accident. I am truly insulted and very frustrated. I was advised to do the latest update from Apple and that was it.
Part of my secondary frustration is, I don't know who is being deleted or how many people I have already lost. It seems to be completely random. Yesterday the contact was there and an hour later when I responded to the text, it was his number only -- and no contact saved in my phone.