I am not 100% sure what is happening in your case, but from experience I can tell you this.
When someone calls and leaves a message longer than 2 minutes in the version that you have, it is not saved. In the new version which should be updated within days, the behavior is that after 2 minutes message will be saved. Now from what you describe I can only assume (since i don't have sufficient info) that there is a possibility that your gateway does not terminate the call when people call. So when people call and put down the phone after leaving a message instead of # 0, what happens is that the gateway possibly does not terminate the call, the line remains open, and after 2 minutes voicemail manager rejects the call and doesn't save.
Can you check if the line remains on, when you close the phone (have someone call in from external number to your gateway)?
Also can you check calling an internal extension, from an extension within the company and leaving voicemail, and closing the phone to see if the voicemail is saved (without # 0) when putting down the phone?
what is the brand/model of your gateway?
I believe that when you dial from extension to extension that this problem will not appear and the message will be saved.