We use Unity with Exchange, but I have also noticed issues when the message store server is rebooted or the message store taken offline. While Unity does recognize that the server is back online, I've noticed sluggish MWI activity and slow response when accessing voicemail through the TUI. I make it a habit to schedule a maintenance window for Unity at the same time as Exchange and reboot the Unity server AFTER the Exchange server is back online.
Brandon