We have intermittent problems with our voicemail notifications being delayed (by a few to many hours) from our Asterisk server to our Exchange 2003 server. We are running Asterisk Business Edition 1.4 on Fedora. What has been happening most recently is no-one received email notifications yesterday for voicemails received yesteday and then they all came through at the same time this morning. I checked the Exchange server and the messages are getting thru no problem as soon as they are being received.
Anybody have any suggestions of how to troubleshoot this?

Asterisk submits the voice message to the mail queue via sendmail as soon as the call is hung up. I would look at the mail daemon logs on your Fedora system in /var/log, it should indicate why it's not able to deliver immediately.
Thanks for the suggestion spditner, I will check it out.