I haven't heard of that before. What we'd need (and this would probably best be worked via a TAC case) would be a copy of the messages.log and atrace.log along with a timestamp of when the problem was noticed (and for what mailbox). If it's an AIM, then the atrace.log won't be written by default (and it might be better to set it up to trace to an external FTP server); for the NM, it's on by default, although depending on how reproducible the problem is, we might want to turn on some voicemail traces, so that we can tell when user logged in and requested the message and such.
If the user listens to the message that showed the delay again, does it always have the gap at the same time/place? That may help indicate if the problem is in recording the message or in playing it back. Also, the only thing I could guess might affect this is if--especially on an AIM--if all traces were turned on. If you do a 'show trace' make sure it doesn't list everything with ffffff as the trace mask.