Exchange is not sending voice mail messages to the users mailbox - they are being held in the voicemail directory queue and this error shows up in the logs:

Log Name:      Application
Source:        MSExchange Unified Messaging
Date:          5/1/2013 6:45:20 PM
Event ID:      1423
Task Category: UMCore
Level:         Error
Keywords:      Classic
User:          N/A
Computer:      SEAvExch1.lan.mydomain.com
Description:
The Unified Messaging server encountered an error while trying to process the message with header file "C:\Program Files\Microsoft\Exchange Server\V14\UnifiedMessaging\voicemail\b0f56c01-94d9-41ee-aa30-df631365e9b3.txt". Error details: "Microsoft.Exchange.UM.UMCore.SmtpSubmissionException: Submission to the Hub Transport server failed. The operation will be retried. ---> Microsoft.Exchange.Net.ExSmtpClient.UnexpectedSmtpServerResponseException: Unexpected SMTP server response. Expected: 220, actual: 500, whole response: 500 5.3.3 Unrecognized command
 
   at Microsoft.Exchange.Net.ExSmtpClient.SmtpTalk.CheckResponse(ServerResponseInfo response, Int32 expectedCode)
   at Microsoft.Exchange.Net.ExSmtpClient.SmtpTalk.Command(SmtpChunk[] chunks, SmtpCommandType command, Int32 expectedCode)
   at Microsoft.Exchange.Net.ExSmtpClient.SmtpTalk.StartTls()
   at Microsoft.Exchange.Net.ExSmtpClient.SmtpClient.Submit(Boolean disableDelayedAck)
   at Microsoft.Exchange.UM.UMCore.SmtpSubmissionHelper.SubmitMessage(MessageItem message, String senderAddress, String recipientAddress, OutboundConversionOptions submissionConversionOptions, InternalExchangeServer smtpServer)
   at Microsoft.Exchange.UM.UMCore.SmtpSubmissionHelper.SubmitMessage(MessageItem message, String senderAddress, String recipientAddress, OutboundConversionOptions submissionConversionOptions, String requestId)
   --- End of inner exception stack trace ---

Server stack trace:
   at Microsoft.Exchange.UM.UMCore.SmtpSubmissionHelper.HandleTransientSmtpFailure(Exception e, InternalExchangeServer smtpServer, String recipientAddress)
   at Microsoft.Exchange.UM.UMCore.SmtpSubmissionHelper.SubmitMessage(MessageItem message, String senderAddress, String recipientAddress, OutboundConversionOptions submissionConversionOptions, String requestId)
   at Microsoft.Exchange.UM.UMCore.SmtpSubmitStage.InternalDoSynchronousWork()
   at System.Runtime.Remoting.Messaging.StackBuilderSink._PrivateProcessMessage(IntPtr md, Object[] args, Object server, Int32 methodPtr, Boolean fExecuteInContext, Object[]& outArgs)
   at System.Runtime.Remoting.Messaging.StackBuilderSink.AsyncProcessMessage(IMessage msg, IMessageSink replySink)

Exception rethrown at [0]:
   at System.Runtime.Remoting.Proxies.RealProxy.EndInvokeHelper(Message reqMsg, Boolean bProxyCase)
   at System.Runtime.Remoting.Proxies.RemotingProxy.Invoke(Object NotUsed, MessageData& msgData)
   at Microsoft.Exchange.UM.UMCore.SynchronousPipelineStageBase.SynchronousWorkDelegate.EndInvoke(IAsyncResult result)
   at Microsoft.Exchange.UM.UMCore.SynchronousPipelineStageBase.EndSynchronousWork(IAsyncResult r)"
Event Xml:
<Event xmlns="http://schemas.microsoft.com/win/2004/08/events/event">
  <System>
    <Provider Name="MSExchange Unified Messaging" />
    <EventID Qualifiers="49156">1423</EventID>
    <Level>2</Level>
    <Task>2</Task>
    <Keywords>0x80000000000000</Keywords>
    <TimeCreated SystemTime="2013-05-02T01:45:20.000000000Z" />
    <EventRecordID>65048</EventRecordID>
    <Channel>Application</Channel>
    <Computer>SEAvExch1.lan.mydomain.com</Computer>
    <Security />
  </System>
  <EventData>
    <Data>C:\Program Files\Microsoft\Exchange Server\V14\UnifiedMessaging\voicemail\b0f56c01-94d9-41ee-aa30-df631365e9b3.txt</Data>
    <Data>Microsoft.Exchange.UM.UMCore.SmtpSubmissionException: Submission to the Hub Transport server failed. The operation will be retried. ---&gt; Microsoft.Exchange.Net.ExSmtpClient.UnexpectedSmtpServerResponseException: Unexpected SMTP server response. Expected: 220, actual: 500, whole response: 500 5.3.3 Unrecognized command
 
   at Microsoft.Exchange.Net.ExSmtpClient.SmtpTalk.CheckResponse(ServerResponseInfo response, Int32 expectedCode)
   at Microsoft.Exchange.Net.ExSmtpClient.SmtpTalk.Command(SmtpChunk[] chunks, SmtpCommandType command, Int32 expectedCode)
   at Microsoft.Exchange.Net.ExSmtpClient.SmtpTalk.StartTls()
   at Microsoft.Exchange.Net.ExSmtpClient.SmtpClient.Submit(Boolean disableDelayedAck)
   at Microsoft.Exchange.UM.UMCore.SmtpSubmissionHelper.SubmitMessage(MessageItem message, String senderAddress, String recipientAddress, OutboundConversionOptions submissionConversionOptions, InternalExchangeServer smtpServer)
   at Microsoft.Exchange.UM.UMCore.SmtpSubmissionHelper.SubmitMessage(MessageItem message, String senderAddress, String recipientAddress, OutboundConversionOptions submissionConversionOptions, String requestId)
   --- End of inner exception stack trace ---

Server stack trace:
   at Microsoft.Exchange.UM.UMCore.SmtpSubmissionHelper.HandleTransientSmtpFailure(Exception e, InternalExchangeServer smtpServer, String recipientAddress)
   at Microsoft.Exchange.UM.UMCore.SmtpSubmissionHelper.SubmitMessage(MessageItem message, String senderAddress, String recipientAddress, OutboundConversionOptions submissionConversionOptions, String requestId)
   at Microsoft.Exchange.UM.UMCore.SmtpSubmitStage.InternalDoSynchronousWork()
   at System.Runtime.Remoting.Messaging.StackBuilderSink._PrivateProcessMessage(IntPtr md, Object[] args, Object server, Int32 methodPtr, Boolean fExecuteInContext, Object[]&amp; outArgs)
   at System.Runtime.Remoting.Messaging.StackBuilderSink.AsyncProcessMessage(IMessage msg, IMessageSink replySink)

Exception rethrown at [0]:
   at System.Runtime.Remoting.Proxies.RealProxy.EndInvokeHelper(Message reqMsg, Boolean bProxyCase)
   at System.Runtime.Remoting.Proxies.RemotingProxy.Invoke(Object NotUsed, MessageData&amp; msgData)
   at Microsoft.Exchange.UM.UMCore.SynchronousPipelineStageBase.SynchronousWorkDelegate.EndInvoke(IAsyncResult result)
   at Microsoft.Exchange.UM.UMCore.SynchronousPipelineStageBase.EndSynchronousWork(IAsyncResult r)</Data>
  </EventData>
</Event>

also seeing a few of these:

Log Name:      Application
Source:        MSExchange Unified Messaging
Date:          5/1/2013 6:37:15 PM
Event ID:      1335
Task Category: UMService
Level:         Error
Keywords:      Classic
User:          N/A
Computer:      SEAvExch1.lan.mydomain.com
Description:
The Unified Messaging server encountered an error while trying to process the message with header file "C:\Program Files\Microsoft\Exchange Server\V14\UnifiedMessaging\voicemail\cdce4a51-7e6f-492a-b00b-1fe985ba78ca.txt". The message will be deleted and the "MSExchangeUMAvailability: % of Messages Successfully Processed Over the Last Hour" performance counter will be decreased. Error details: "Microsoft.Exchange.Data.Common.LocalizedException: The Header file (C:\Program Files\Microsoft\Exchange Server\V14\UnifiedMessaging\voicemail\cdce4a51-7e6f-492a-b00b-1fe985ba78ca.txt) either doesn't exist or has been removed.".
Event Xml:
<Event xmlns="http://schemas.microsoft.com/win/2004/08/events/event">
  <System>
    <Provider Name="MSExchange Unified Messaging" />
    <EventID Qualifiers="49156">1335</EventID>
    <Level>2</Level>
    <Task>4</Task>
    <Keywords>0x80000000000000</Keywords>
    <TimeCreated SystemTime="2013-05-02T01:37:15.000000000Z" />
    <EventRecordID>64978</EventRecordID>
    <Channel>Application</Channel>
    <Computer>SEAvExch1.lan.mydomain.com</Computer>
    <Security />
  </System>
  <EventData>
    <Data>C:\Program Files\Microsoft\Exchange Server\V14\UnifiedMessaging\voicemail\cdce4a51-7e6f-492a-b00b-1fe985ba78ca.txt</Data>
    <Data>Microsoft.Exchange.Data.Common.LocalizedException: The Header file (C:\Program Files\Microsoft\Exchange Server\V14\UnifiedMessaging\voicemail\cdce4a51-7e6f-492a-b00b-1fe985ba78ca.txt) either doesn't exist or has been removed.</Data>
  </EventData>
</Event>