RLyon,
Well, it has nothing to do with the Message key itself if it is sending them to the actual Voice Processor; like it is supposed to.
Anyway, you need to look at logs and see what the Voice Processor is doing.
Also, look at the prompts and make sure no one has deleted them. Sometimes there is a problem on upgrades which is why I also reload the prompts during that time.
If you know how to look at System Commands then you could go that route as well to see what the VP is doing, but for most I think looking at the logs is the easiest thing.
If it is only one mailbox doing this and all of the others are working as expected then it might just be easier to delete and recreate the mailbox.
If you are not sure then I would have them log into a different persons mailbox and see if it works as expected there. Also, have someone else log into this person's mailbox from their phone and see if the problem follows the mailbox or the phone. You could also have them call in from outside of the system and check their mailbox that way as well. This will tell you what you would need to know going forward as it seems you didn't do any basic testing yet.
Thanks,
TE