What type of voicemail system are you using, Unity/Unity Connection/CUE?  Can the user dial the MWI on number directly and turn on the MWI light?  Make sure that the voicemail ports can reach the MWI number based on the CSS/partition configuration, and that the MWI on number can reach the phone for starters.  Then something that's not as obvious if this used to work looks for any translation patterns that may be matched by the MWI on number instead of the phone's directory number.