My issue with some contacts not wanting to sync was only related to how their numbers were saved in contacts.

I have to have +46 in front of the number which is my country code or the contacts won't sync. I just edited some numbers, synced again and now everyone is found.