I noticed a similar issue when adding contacts from apps (like maps, poynt, etc). I logged into my gmail account, went to contacts tab, checked all in "other contacts" and clicked "add to My Contacts". With the next sync all of those contacts started showing up in the android contact list. Apparently, some numbers get added to "other contacts" instead of "my contacts" and the phone only syncs with "my contacts".