Do the DN's overlap ?? With the info provided it would be tough for to state what could be the issue. One of the most common issues in such cases could be Partitions/CSS. If Unity shows MWI On, then if you could collect CCM detailed traces when the message is left for a user (+ and -5 mins) along with the info about the MWI On/Off #, Partition assigned to the DN and DN where the MWI is not working, it would help to try and identify the problem