Contacts not matching/syncing correctly between devices

When iCloud came along, I assumed I could just turn it on for contacts and everything would sync up. This did not work. iOS (6 at the time) assumes the locally stored contacts will stay local (not shared). That you want to have the privacy of unshared contacts and it waits for you to tell it what are 'public'.

For each device, I had to move them over to the 'icloud side' of things and delete them from the local side. And it wasnt until the last local contact was deleted that everything defaulted over to icloud. (shared only). Its been to long now that I dont recall the process, but perhaps that will give you enough, or someone else does.

 

It does sound like you've got contacts that are in a group other than the one you're syncing. As ElectronGuru said, put everything into that one group (iCloud, Google or whatever) and get rid of the ones that reside on the device-only.