Make sure you're including the 9* at the beginning of the dial string.
Must have lines assigned to the VM ports, and not restricted.
Put Auto-Intercom buttons on a phone for the VM ports, watch to see if it goes off hook after a message is left. Monitor the CO line with a butt set to listen to what it dials, and see if the call goes through or fails at the telco level.