Most of the time when I see this it's because the message didn't come from "their" mailbox but rather from some other mbox that notifies their station (hunt group, general night mailbox etc.). Press the lit message key without going off-hook first, it should tell you what mbox left the message. Then fix password for that one.
Database programming will also tell you in the SUBSCRIBER STATISTICS section whether he really has a message.