Make sure the call is going to the same voice mail box when calling from the outside. I guess this is true if you are hearing the same greeting before leaving a message or you can use RTMT to monitor the voice mail port when leaving a message.
This thread talks about checking the SMTP address for the user but not sure if this is what causing your issue.
https://supportforums.cisco.com/message/1230529#1230529
Please rate helpful answers!