It sounds to me as if 6000 was never intended to be dialed externally.
Are you sure that number is in your DID range?
I'd bet that if you looked in your system speed dials you may find a different number pointing to 6000. Try dialing those from the outside.
Oh, by the way, what type of voice mail are you using?
Ralph