I have just encountered a similar problem. One of my daughters-in-law has disappeared from the contacts on my phone, both in the general contacts and in the list of starred contacts. Oddly, her name still appears in my gmail contact list in the cloud -- when I access my contacts from a browser on my computer, it is right there, both in the starred list and the general list.
It gets odder yet: If I add a new contact for her on the phone, the new contact immediately disappears (or perhaps just becomes invisible) but still syncs over to the cloud and shows up on my desktop.
And it gets even odder yet: If I pull up her contact on my computer and change her first name by adding an extra letter (JJamie instead of Jamie), that change immediately syncs over to the phone and her contact reappears on the phone. But if I delete the extra letter in her first name, changing it back to "Jamie," the contact immediately disappears from the phone again.
I, too, would appreciate any ideas or theories anyone out there might have, however wild and creative. I depend on the phone for my work and this is destroying my confidence in this tool -- I am concerned that other contacts may also be disappearing or becoming invisible and that I might not notice until I am in an emergency situation.
FWIW, I do have a lot of contacts, mostly for work -- between 550 and 600.