Akuhn,
There are a few things that can cause that issue and depending on the real problem there may be some fixes for them.
1. It really could be that the callers side is having connection problems as you were told, nothing we can do about that.
2. They may be exceeding the capacity of the mailbox when leaving a message. Check which users are experiencing the issue the most and see how full their mailbox is, increase its capacity, default 30 minutes, or have them clear out their messages. You can find that limit in each mailbox.
3. They could be experiencing what we call talk off, where it recognizes a button press during the conversation, in this 0 which is the only button allowed in a mailbox. This is not a fix for a user get your dealer involved. If you want to try do a search for DTMF High and Low Twists on this site as I know I have posted on this issue before and put in some detailed notes. Those notes will mostly refer to Call Routing Announcements where this issue normally occurs. If you are not having that issue with CRAs then this is most likely not your issue.
4. It could also be recognizing silence and disconnecting. The default for this is 5 seconds, but someone may have lowered it so look under the Voice Processors Timers and Limits.
Thanks,
TE