We recently started having trouble with our voicemail system failing after we rebooted our Cisco Unity server.  It turned out that every time we would reboot the Unity server, the Microsoft Message Queuing Service would hang on startup causing the voicemail to fail.  While on the phone with Cisco technical support, We were informed that if the MSMQ folder (located on Unity at C:\WINNT\System32\msmq) gets larger than 1.5 GB, then the service will never start. [more]We looked at it, and sure enough, it was 1.56 GB. After some trial and error of removing the files in the folder, trying to start the service, failing, and putting the files back in, he finally informed us that we would probably have to reinstall the service.

We reinstalled the Microsoft Message Queuing Service, and the voicemail system started right up. Since then, we have not any high CPU usage problems, no extreme lagging in the voicemail system (that I know about), and hardly any delays in the administration website.