Hi Peterson,
It's hard to say without some more information. You will not get MWI until the message successfully reaches the Exchange mailbox.
Is Exchange on-box, or off-box? Unified or Voice Mail Only?
Is this happening for 100% of the users?
Do you see the messages stuck in the Commserver\UnityMTA directory for these users?
Have you tested whether or not this happens for only external, or only internal, or both types of calls?
What errors/warnings are you getting in the application log?
You can always re-run the Message Store Configuration Wizard, it will need to bring Unity's services down when its ran but will then restart them once completed.
Hope that helps,
Brad