Problems here too, bought a new Android phone, Lollipop, set to display ALL contacts, some are missing from the new phone, and some are on both phones but on the new one they lack some part, e.g. I only have the mobile number where I also (really) need the home number and address.
I _do_ have a backup but in the past already found myself under checkmate: 1) the app I used was also loosing contacts, so I could not avoid using the google sync feature; 2) restoring from backup (e.g. after a factory reset) in order to also have the contacts lost by google sync was giving me me twice (or more times) the contacts which were not lost by google sync, the backup/restore app was not recognizing doubles and thus not merging.
As probably all of us, I have a whole lot of things to do (more or less interesting and more or less important/vital), I will not be able to investigate further for now and will not be able to sit down and stay cross checking through the whole lot of contacts I stored during various years, so I'll probably end up keeping two phones with me, at least for a while.
I see this thread as been on for quite some time, so there doesn't seem to be any will to fix this issue with the urgence it deserves.
For the future, apart considering a not-Android phone (not Apple either), I'd probably stay on this line: investigate to find out a *good* app to store contacts backup (I mean better/smarter than the one I was using and which does not loose any contact), and if none is smart enough to recognize and merge doubles then I'll opt to *not* let Google sync any contacts, at least I'd have a clean situation on which operate backup/restore, with no mess incoming from the cloud because of badly implemented critical tasks.