Here is the thread I had stated on a similar issue. Basically Voicemail would ring to dead air, but the service was still running. The logs show that the IPO lost it's connection with the VMServer for some reason. I have sample logs in that thread also.
I was using 4.1.9, and tried all different flavors of VM. 4.1.27 was the first, I downgraded to 4.0 VM, still had the problem, I moved the VM Server to a new server, happened more often, moved it back to the original server.. 4.1.12/40 came out, didn't happen for a week, then had it happen again.
I am part of a Domain, so my check box for Internet Time sync was not there, but I had the Time Server set to the VM Server, and the VM Server would get it's time from the Domain Controller on-site, and the Domain Controller should have gotten it's time from our Router but, for some reason when you checked what the time server was for the D.C, it was blank. So, I changed the Time Server on the IPO to the router, and haven't had this problem since.. 3 weeks now.. *crosses fingers*