What are your extension numbers, and the maximum extension length set in the voice mail?
If, for instance, you have 2 digit extension numbers, but the voice mail is set for 3 digits maximum, it will need to time out before deciding that the caller is done dialing.