We recently upgraded to CUM 7 from Unity 4. Big difference.

In doing so, we also get our voicemails sent to our Exchange 2007 inbox as well as having the red light show up on our IP Phones. I recently, for the first time in about 6 weeks, rebooted our primary Exchange server. Unity did not like this, and all voicemail alerts (the red light) failed to work.

The fix for this is:
RDP to the UM server as a Unity Administrator – make sure you don’t allow sounds to go back and forth over the RDP connection as this would make all voicemails fail.
Start, All Programs, Unity, Manage Integrations
If you get an alert that the services cannot be found, then you are probably not logged in as a Unity Admin (or the services really are off, in which case you would have a much larger problem)
Now navigate down to the Properties of your CUCM/CCM server.
In the lower right corner there should be a MWI Resynchronize Now button. Press this button.

Depending on the size of your organization this could take up to a couple minutes.