I ran into this issue and thought I'd post a reply even though this is a few months old at this point. I searched vigorously online for a solution, but to no avail. I finally decided to take matters into my own hands. I started playing around with my contacts in Outlook on my PC and noticed that when I updated one of them, a subsequent sync on my phone would retrieve the contact. With this in mind, I exported my contacts, imported them again, and ran a sync. Voila! Problem solved. Here are the steps:
DISCLAIMER: This process does not preserve photos or groups. If your contact photos are extremely important to you, or you don't feel like setting up your groups again, I'd suggest more research.
1. Go to the Outlook website, login, click the drop-down in the upper left-hand corner, and choose People.
2. Click Manage and choose "Export for Outlook.com and other services"
3. You'll be prompted to download a file called OutlookContacts.csv. Save this somewhere easy to find.
4. Click the checkbox labeled "All" near the upper right-hand corner. This will select all of your contacts. If there are any groups you want preserved, uncheck them from the list. These will not be imported in Step 7.
5. Click the Delete menu item and click the subsequent confirmation button. I know, this is the scary part. If you want to perform a sanity check, you can find the file you downloaded and ensure that it opens in Excel and displays all of your contacts before taking the plunge. If you don't have Excel, you can open the file in Notepad. It won't be formatted like it would be in Excel, but you'll be able to verify that your contacts are present.
6. At this point, I performed a sync on my phone to ensure that my contact list was emptied. This step may not be necessary, but I'd recommend it.
7. Click the People button in the upper right-hand corner. This will take you to the main page, showing a few options you have on the right.
8. Click the Start Import button under the Import Contacts header.
9. Choose Outlook.com on the page you're taken to.
10. Click the Browse button and select the OutlookContacts.csv file.
11. The website will report that your contacts were imported and you'll see them once again in the right-hand menu.
12. Sync your phone. (Open the People app, expand the menu, choose Settings, select Add Contacts, long press Microsoft Account (or Outlook, Hotmail, etc.), choose Sync from the resulting menu.)
13. You'll see that the state switches to syncing. Once this is complete, go back to your People app. You should see all of your accounts.
I hope this helps!