First, you need to make sure that the contacts that you are expecting to sync are actually stored in Exchange. In your case, you could have had contacts stored in 3 different locations: 1) locally on your iPhone, 2) in iCloud,, 3) on Exchange server.
To ensure that your contacts are actually in exchange, use Exchange Web Access to check that the contacts in question are actually on the Exchange server.
Then, on your iPhone, go to "Contacts" app > "Groups" > and make sure that your Exchange account is enabled for display.
It is sometimes helpful to disable all server-based accounts in "Groups" to see what contacts are actually stored locally on the phone. You can then enable one account at a time to see which additional contacts show up.