This can be the case if the user's Outlook is set up to mark the message as "Read" immediately on receipt. This is then no longer considered a new message, and the MWI will never come on.
Check the Outlook settings. Another possibility is if the user has rules that moves the message out of the Inbox; once the message is out of the Inbox, then from the phone perspective it is gone.
Eric