Hi Rich,

Base on my research, it may be caused by a corrupted mailbox.

Please run the following command and check if any helps:

New-MailboxRepairRequest -Database "mailbox database name" -CorruptionType SearchFolder,AggregateCounts,ProvisionedFolder,FolderView

Use the New-MailboxRepairRequest cmdlet to detect and fix mailbox corruptions. You can run this command against a specific mailbox or against a database. While this task is running, mailbox access is disrupted only for the mailbox being repaired. If you're running this command against a database, only the mailbox being repaired is disrupted. All other mailboxes on the database remain operational.

Best regards,

OK,   I'm trying this now,   

If this helps, I also found the following datapoint:

[PS] C:\Windows>Get-ServerHealth -Identity IT-5037   | where { $_.alertvalue -eq "unhealthy"} | ft -auto -wrap

Server  State         Name                               TargetResource HealthSetName    AlertValue ServerComponent
------  -----         ----                               -------------- -------------    ---------- ---------------
IT-5037 NotApplicable MailboxDeliveryAvailabilityMonitor                MailboxTransport Unhealthy  None


[PS] C:\Windows>Invoke-MonitoringProbe  Mailboxtransport\MailboxDeliveryInstanceAvailabilityProbe -server IT-5037 | fl


RunspaceId         : 9db02755-2586-4982-ac70-b8e8ac1a165e
Server             : IT-5037
MonitorIdentity    : Mailboxtransport\MailboxDeliveryInstanceAvailabilityProbe
RequestId          : f6d76123-114d-4d48-8525-5c55526d2633
ExecutionStartTime : 9/1/2015 12:58:03 PM
ExecutionEndTime   : 9/1/2015 12:58:03 PM
Error              : The given key was not present in the dictionary.
Exception          : System.Collections.Generic.KeyNotFoundException: The given key was not present in the dictionary.
                        at System.Collections.Generic.Dictionary`2.get_Item(TKey key)
                        at Microsoft.Forefront.Monitoring.ActiveMonitoring.Smtp.Probes.MailboxDeliveryInstanceAvailabil
                     ityProbe.BeforeConnect()
                        at Microsoft.Forefront.Monitoring.ActiveMonitoring.Smtp.Probes.SmtpConnectionProbe.MeasureLaten
                     cy(String reason, Action cmd)
                        at Microsoft.Forefront.Monitoring.ActiveMonitoring.Smtp.Probes.SmtpConnectionProbe.DoWork(Cance
                     llationToken cancellationToken)
                        at Microsoft.Office.Datacenter.WorkerTaskFramework.WorkItem.Execute(CancellationToken
                     joinedToken)
                        at
                     Microsoft.Office.Datacenter.WorkerTaskFramework.WorkItem.<>c__DisplayClass2.<StartExecuting>b__0()
                        at System.Threading.Tasks.Task.Execute()
PoisonedCount      : 0
ExecutionId        : 25476728
SampleValue        : 0
ExecutionContext   :
FailureContext     : The given key was not present in the dictionary.
ExtensionXml       :
ResultType         : Failed
RetryCount         : 0
ResultName         : f6d76123114d4d4885255c55526d2633-MailboxDeliveryInstanceAvailabilityProbe
IsNotified         : False
ResultId           : 27276720
ServiceName        : InvokeNow
StateAttribute1    :
StateAttribute2    :
StateAttribute3    :
StateAttribute4    :
StateAttribute5    :
StateAttribute6    : 0
StateAttribute7    : 0
StateAttribute8    : 0
StateAttribute9    : 0
StateAttribute10   : 0
StateAttribute11   : The connection has not been established
StateAttribute12   : No latencies were above the standard deviation. Mean: 0 Standard Deviation: 1
StateAttribute13   : BeforeConnect=0
StateAttribute14   :
StateAttribute15   :
StateAttribute16   : 0
StateAttribute17   : 0
StateAttribute18   : 0
StateAttribute19   : 0
StateAttribute20   : 0
StateAttribute21   : System.Collections.Generic.KeyNotFoundException
StateAttribute22   :
StateAttribute23   :
StateAttribute24   :
StateAttribute25   :
Identity           : 3a2d70f1325142f3a2b7c1411ba19c82
IsValid            : True
ObjectState        : New

Ran this command against the Store,  Unfortantly it hasn't resolved the error.

Additional Event information.

Microsoft Exchange Information Store worker process (12092) has encountered an unexpected database error (Microsoft.Isam.Esent.Interop.EsentKeyDuplicateException: Illegal duplicate key
   at Microsoft.Isam.Esent.Interop.Server2003.Server2003Api.JetUpdate2(JET_SESID sesid, JET_TABLEID tableid, Byte[] bookmark, Int32 bookmarkSize, Int32& actualBookmarkSize, UpdateGrbit grbit)
   at Microsoft.Exchange.Server.Storage.PhysicalAccessJet.JetTableOperator.Insert(IList`1 columns, IList`1 values, Column identityColumnToFetch, Boolean unversioned, Boolean ignoreDuplicateKey, Object& identityValue)) for database 'H-Check' with a call stack of
   at Microsoft.Exchange.Server.Storage.PhysicalAccessJet.JetTableOperator.Insert(IList`1 columns, IList`1 values, Column identityColumnToFetch, Boolean unversioned, Boolean ignoreDuplicateKey, Object& identityValue)
   at Microsoft.Exchange.Server.Storage.PhysicalAccessJet.JetInsertOperator.ExecuteScalar()
   at Microsoft.Exchange.Server.Storage.PhysicalAccess.DataRow.Insert(IConnectionProvider connectionProvider)
   at Microsoft.Exchange.Server.Storage.StoreCommonServices.ObjectPropertyBag.Flush(Context context)
   at Microsoft.Exchange.Server.Storage.LogicalDataModel.Item.Flush(Context context)
   at Microsoft.Exchange.Server.Storage.LogicalDataModel.Message.Flush(Context context)
   at Microsoft.Exchange.Server.Storage.LogicalDataModel.Message.SaveChanges(Context context)
   at Microsoft.Exchange.Server.Storage.LogicalDataModel.TopMessage.SaveChanges(Context context, SaveMessageChangesFlags flags)
   at Microsoft.Exchange.Server.Storage.LogicalDataModel.Conversations.TrackConversationUpdateForMessageInsert(Context context, Mailbox mailbox, TopMessage message, ModifiedSearchFolders modifiedSearchFolders)
   at Microsoft.Exchange.Server.Storage.LogicalDataModel.Conversations.TrackConversationUpdate(Context context, Mailbox mailbox, TopMessage message, LogicalOperation operation, ModifiedSearchFolders modifiedSearchFolders)
   at Microsoft.Exchange.Server.Storage.LogicalDataModel.TopMessage.TrackUpdate(Context context, LogicalOperation operation, Nullable`1 userIdentityContext)
   at Microsoft.Exchange.Server.Storage.LogicalDataModel.TopMessage.OnAfterDataRowFlushOrDelete(Context context, Boolean delete)
   at Microsoft.Exchange.Server.Storage.StoreCommonServices.ObjectPropertyBag.Flush(Context context)
   at Microsoft.Exchange.Server.Storage.LogicalDataModel.Item.Flush(Context context)
   at Microsoft.Exchange.Server.Storage.LogicalDataModel.Message.Flush(Context context)
   at Microsoft.Exchange.Server.Storage.LogicalDataModel.Message.SaveChanges(Context context)
   at Microsoft.Exchange.Server.Storage.LogicalDataModel.TopMessage.SaveChanges(Context context, SaveMessageChangesFlags flags)
   at Microsoft.Exchange.Protocols.MAPI.MapiMessage.SaveChangesInternal(MapiContext context, MapiSaveMessageChangesFlags saveFlags, ExchangeId& newMid)
   at Microsoft.Exchange.Protocols.MAPI.MapiMessage.SaveChanges(MapiContext context, MapiSaveMessageChangesFlags saveFlags, ExchangeId& newMid)
   at Microsoft.Exchange.Protocols.MAPI.MapiMessage.Deliver(MapiContext context, RecipientType recipientType, ExchangeId& mid)
   at Microsoft.Exchange.Server.Storage.MapiDisp.RopHandler.TransportDeliverMessage2(MapiContext context, MapiMessage message, TransportRecipientType transportRecipientType, TransportDeliverMessage2ResultFactory resultFactory)
   at Microsoft.Exchange.Server.Storage.MapiDisp.RopHandlerBase.TransportDeliverMessage2(IServerObject serverObject, TransportRecipientType recipientType, TransportDeliverMessage2ResultFactory resultFactory)
   at Microsoft.Exchange.RpcClientAccess.Parser.RopTransportDeliverMessage2.InternalExecute(IServerObject serverObject, IRopHandler ropHandler, ArraySegment`1 outputBuffer)
   at Microsoft.Exchange.RpcClientAccess.Parser.InputRop.Execute(IConnectionInformation connection, IRopDriver ropDriver, ServerObjectHandleTable handleTable, ArraySegment`1 outputBuffer)
   at Microsoft.Exchange.RpcClientAccess.Parser.RopDriver.ExecuteRops(List`1 inputArraySegmentList, ServerObjectHandleTable serverObjectHandleTable, ArraySegment`1 outputBuffer, Int32 outputIndex, Int32 maxOutputSize, Boolean isOutputBufferMaxSize, Int32& outputSize, AuxiliaryData auxiliaryData, Boolean isFake, Byte[]& fakeOut)
   at Microsoft.Exchange.RpcClientAccess.Parser.RopDriver.Execute(IList`1 inputBufferArray, ArraySegment`1 outputBuffer, Int32& outputSize, AuxiliaryData auxiliaryData, Boolean isFake, Byte[]& fakeOut)
   at Microsoft.Exchange.Server.Storage.MapiDisp.MapiRpc.<>c__DisplayClass9.<DoRpc>b__6(MapiContext operationContext, MapiSession& session, Boolean& deregisterSession, AuxiliaryData auxiliaryData)
   at Microsoft.Exchange.Server.Storage.MapiDisp.MapiRpc.Execute(IExecutionDiagnostics executionDiagnostics, MapiContext outerContext, String functionName, Boolean isRpc, IntPtr& contextHandle, Boolean tryLockSession, String userDn, IList`1 dataIn, Int32 sizeInMegabytes, ArraySegment`1 auxIn, ArraySegment`1 auxOut, Int32& sizeAuxOut, ExecuteDelegate executeDelegate)
   at Microsoft.Exchange.Server.Storage.MapiDisp.MapiRpc.DoRpc(IExecutionDiagnostics executionDiagnostics, IntPtr& contextHandle, IList`1 ropInArraySegments, ArraySegment`1 ropOut, Int32& sizeRopOut, Boolean internalAccessPrivileges, ArraySegment`1 auxIn, ArraySegment`1 auxOut, Int32& sizeAuxOut, Boolean fakeRequest, Byte[]& fakeOut)
   at Microsoft.Exchange.Server.Storage.MapiDisp.PoolRpcServer.EcDoRpc(MapiExecutionDiagnostics executionDiagnostics, IntPtr& sessionHandle, UInt32 flags, UInt32 maximumResponseSize, ArraySegment`1 request, ArraySegment`1 auxiliaryIn, IPoolSessionDoRpcCompletion completion)
   at Microsoft.Exchange.Server.Storage.MapiDisp.PoolRpcServer.EcPoolSessionDoRpc_Unwrapped(MapiExecutionDiagnostics executionDiagnostics, IntPtr contextHandle, UInt32 sessionHandle, UInt32 flags, UInt32 maximumResponseSize, ArraySegment`1 request, ArraySegment`1 auxiliaryIn, IPoolSessionDoRpcCompletion completion)
   at Microsoft.Exchange.Server.Storage.MapiDisp.PoolRpcServer.<>c__DisplayClassf.<EcPoolSessionDoRpc>b__c()
   at Microsoft.Exchange.Common.IL.ILUtil.DoTryFilterCatch[T](TryDelegate tryDelegate, GenericFilterDelegate filterDelegate, GenericCatchDelegate catchDelegate, T state)
   at Microsoft.Exchange.Server.Storage.MapiDisp.PoolRpcServer.EcPoolSessionDoRpc(IntPtr contextHandle, UInt32 sessionHandle, UInt32 flags, UInt32 maximumResponseSize, ArraySegment`1 request, ArraySegment`1 auxiliaryIn, IPoolSessionDoRpcCompletion completion)
   at EcPoolSessionDoRpcRpc.EcDispatchCall(EcPoolSessionDoRpcRpc* , SafeRpcAsyncStateHandle pAsyncState, IPoolRpcServer server)
   at PoolRpcServer_Wrapper.InternalExecute(PoolRpcServer_Wrapper* , SafeRpcAsyncStateHandle pAsyncState)
   at Microsoft.Exchange.Rpc.ManagedExceptionAsyncCrashWrapper.Execute<class Microsoft::Exchange::Rpc::PoolRpc::SafeEcPoolSessionDoRpcRpcAsyncStateHandle>(ManagedExceptionAsyncCrashWrapper* , _RPC_ASYNC_STATE* pAsyncState)
   at EcPoolSessionDoRpc_Managed(_RPC_ASYNC_STATE* pAsyncState, Void* cpxh, UInt32 ulSessionHandle, UInt32* pulFlags, UInt32 cbIn, Byte* rgbIn, UInt32* pcbOut, Byte** ppbOut, UInt32 cbAuxIn, Byte* rgbAuxIn, UInt32* pcbAuxOut, Byte** ppbAuxOut)
.

Hi Rich,

You can try to move all mailboxes to another database and unmount the old database , check if any helps.

Best regards,

I had come up with the same solution last night,   So this morning, I moved all the mailboxes to a different database, Dismounted the MB Store,   Deleted The Store & Created a New one.

No Longer getting the error, and the system is healthy again.

Additional Notes:  With no mailboxes in the store (Event Soft deleted ones) I was still getting the error.

So it seems that it was something with the DataStore itself.

THanks for the Help