I've seen this a few times too, on both Linux and Windows VM Pro servers. With the Linux servers it seemed to be network congestion, if the communication between the IPO and Linux box was slow or dropped it would not reestablish without rebooting the Linux box. To prove this we connected the Linux box directly to the IPO's WAN port, taking the network out of the picture and that cleaned up all of the issues, the voicemail ran flawlessly. Obviously this was not a permanent solution but we used it to prove the customer's network was at fault. We provided a 4 port switch and connected it to the IPO, Linux box, and customer's network. The IPO and Linux box could now communicate without network congestion.
On Windows servers I have gone to Services - Voicemail Pro Service - right clicked, selected one of the tabs (can't remember which one) and set the re-start options. The first two to restart the service, the third one to restart the PC. Since doing that we have never had a problem.