iMessage out of whack... how to "reset"
It's an issue with OS X &amp; Exchange sync. As a workaround, you can use the OWA app by Microsoft to sync your contacts to iCloud:

On iOS there's an app called OWA. Within the app there's a setting within the People section for sync'ing your contacts. Basically it creates a new group in your iCloud called OWA that is a carbon copy of your contacts.

Once I turned this on and saw it sync with my laptop, I got my names resolved and showing in iMessage again!

I have documented a more complete explanation and resolution in Resolving Contacts Sync on OS X - Error SOAPWebServicesErrorDomain.