I have to ask, have you verified that all the contacts are available via the Outlook/Live/Hotmail web interface? Are you using Outlook desktop with MAPI connector? If so, close out Outlook desktop for awhile and let you phone sync.
I found that Outlook desktop with MAPI sometimes dead locks the contacts so your phone won't pull them down or update them.