i think this may be a wider problem with Exchange contact on OSX Snow Leopard that i have been struggling with for a long time and have pretty much given up on with regards to finding a solution.
If you use Skype could you check if your Exchange contacts show up in the Address Book section within Skype? If not then I'd guess its the same wider issue and not related to a single app but instead to how OSX is syncing to Exchange. I have started using Outlook for much of my Exchange interaction (although still like and use Mail) and I seem to have the same problem. Only when a contact is updated (i.e. edited on the local machine) and not necessarily copied to the local machine does it show up. You can verify all this in spotlight searches as you will likely find the same issue with those that do and don't show up. See here for more: https://discussions.apple.com/message/10077002#10077002
