Message recording quality sounds like the person is underwater. This has occured in the last two weeks. We have been making changes to the WAN QoS, but only significant improvements in voice calls across the WAN have resulted, so I can't image that would be the cause.
The first time this happened we reset Unity and the problem seemed to go away, but we're not entirely sure. At any rate, the problem definitely resurfaced 3 or 4 days later. (The reset may not have done anything as the users can't give a definite time as when this happened).
This does not happen on every call. Because most of their callers who leave messages come from the PSTN, we don't know the ratio of band internal messages to bad external messages.
We are running Call Manager 3.2.2spE. Unity 3.1.5
The topology is thus: PSTN via PRI to VG200 to phones. If call goes to voicemail here is the path: PSTN via PRI to VG200 to router across 786k Frame Relay WAN link to VG200 transcoder/DSP Farm to Unity.
As you can image, G.729 across the WAN, transcoded by the DSP farm to G.711, then to Unity. The DSP farm has never seemed to be an issue, though it isn't ruled out yet.
512 MB of RAM on Unity, it is serving under 50 people. It is also running Active Directory.