Is the user online with Exchange when the message is changed to "Read"?
Have you checked to be sure the user's Outlook is not in "cache" mode?
Laptops that frequently use offline stores have these issues, mainly because Exchange doesn't see the changes until it synchs up with the Outlook.
the other issue I see often (as it happens in my case, I just live with it), is that the email comes in to Exchange and is sent to my Blackberry immediately. But, Outlook has a rule that moves the email to a different folder. A folder that I don't synch with. Now these emails are copies, but have no relationship.
My best friend in that case is to move to the Date line on the blackberry, press the trackball, and select Mark Prior Opened.
Being a BES Administrator can be tough, I know. I've had this BES for over 2 years now, and I still learn something new every time a problem appears....