I recently had an Exchange 2010 server fail and I have replaced it with a completely new Exchange 2013 server running on Server 2012 R2. I have been getting complaints that mail flow can be extremely slow. And by slow I mean it could be a day or more before the recipient receives the message. And this is mail being sent from one user in our organization to another user in our organization. Can anyone think of why this is happening and I need to do to fix it?

Not sure how you replaced a failed 2010 server with a 2013 server. How was that accomplished exactly?

For message delays, check message tracking and the internet headers of the messages themselves. Which hop is the delay? Post some examples.

Here is one of the delivery reports. As you can see on 4/2 it took two minutes for the server to process and deliver the message to the user mailbox. However, the user is telling me that they did not receive the message until 4/6.

Delivery Report for  Last Name, First Name (user@domain.org)

Submitted
4/2/2015 11:40 AM Exchange server name
The message was submitted to exchange server.domain.local.

Pending
4/2/2015 11:40 AM Exchange Server.domain.local
Message was received by Exchange Server.domain.local from Exchange Server.domain.local.

4/2/2015 11:42 AM exch2010.usd108.local
The message has been transferred from Exchange Server.domain.local to Exchange Server.domain.local.

Delivered
4/2/2015 11:42 AM Exchange Server.domain.local
The message was successfully delivered.

Here is the internet header for on of the so called delayed emails.

Received: from Exchange Server.domain.local (Internal server IP) by Exchange Server.domain.local
 (Internal Server IP) with Microsoft SMTP Server (TLS) id 15.0.847.32 via Mailbox
 Transport; Thu, 2 Apr 2015 11:16:43 -0500
Received: from Exchange Server.domain.local (Internal Server IP) by Exchange Server.domain.local
 (Internal Server IP) with Microsoft SMTP Server (TLS) id 15.0.847.32; Thu, 2 Apr 2015
 11:16:19 -0500
Received: from Exchange Sever.USD108.local ([::1]) by Exchange Server.Domain.local ([::1])
 with mapi id 15.00.0847.030; Thu, 2 Apr 2015 11:16:19 -0500
Content-Type: application/ms-tnef; name="winmail.dat"
Content-Transfer-Encoding: binary
From: "Sending User" <Sending User@domain.org>
To: Multiple internal users
CC: Multiple external contacts
Subject: Subject
Thread-Topic: same as subject
Thread-Index: AdBtXDyRbHekkEE3RGG7sCyCl5n7pw==
Date: Thu, 2 Apr 2015 11:16:18 -0500
Message-ID: <8a2a2e4dbddd4b2f9339e1833eeaf3b3@Exchange Server.Domain.local>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-Exchange-Organization-SCL: -1
X-MS-TNEF-Correlator: <8a2a2e4dbddd4b2f9339e1833eeaf3b3@Exchange Server.Domain.local>
MIME-Version: 1.0
X-MS-Exchange-Organization-MessageDirectionality: Originating
X-MS-Exchange-Organization-AuthSource: Exchange Server.Domain.local
X-MS-Exchange-Organization-AuthAs: Internal
X-MS-Exchange-Organization-AuthMechanism: 04
X-Originating-IP: [External IP address]
X-MS-Exchange-Organization-Network-Message-Id: 2b0d76ba-648e-4780-b9df-08d23b777cc2
Return-Path: Sending User@domain.org
X-MS-Exchange-Organization-AVStamp-Enterprise: 1.0

Are the users in Outlook cache mode? Are the messages delivered timely if OWA or Online Outlook mode is used?

Try creating a new Outlook profile or delete the cache *.ost file and re-open Outlook and see if the problem continues...

Hi,

Basis on the delivery report and message header, it looks normally.

Therere much more factors that are relate to Exchange performance, for example network and hardware. Please pay attention to Exchange 2013 system requirements, for your reference:
http://technet.microsoft.com/en-us/library/aa996719(v=exchg.150).aspx

By the way, we can run Get-ServerHealth Identity server name to check the health information for Exchange server. More details about Server health and performance, please refer to:
http://technet.microsoft.com/en-us/library/jj150551(v=exchg.150).aspx
http://technet.microsoft.com/en-us/library/jj150524(v=exchg.150).aspx

Thanks

When I run "Get-ServerHealth Identity server name" in the results I can see some unhealthy results but they scroll by so fast that I cannot determine exactly what is unhealthy and I cannot scroll up far enough to see it either.

Here is the list of items that came back either Unhealthy or Disabled

[PS] C:\Windows\system32>Get-ServerHealth -Identity Server

Server          State           Name                 TargetResource       HealthSetName   AlertValue ServerComp
                                                                                                     onent
------          -----           ----                 --------------       -------------   ---------- ----------
Server        NotApplicable   ActiveSyncCTPMonitor ActiveSync           ActiveSync      Unhealthy  None
Server        NotApplicable   AutodiscoverCtpMo... Server.USD108.l... Autodiscover    Unhealthy  None
Server        NotApplicable   AutodiscoverSelfT... MSExchangeAutoDis... Autodiscover... Unhealthy  None
Server        NotApplicable   ActiveSyncDeepTes... ActiveSync           ActiveSync.P... Unhealthy  None
Server        Offline         AutodiscoverProxy... MSExchangeAutodis... Autodiscover... Unhealthy  AutoDis...
Server        Offline         ActiveSyncProxyTe... MSExchangeSyncApp... ActiveSync.P... Unhealthy  ActiveS...
Server        Offline         EWSProxyTestMonitor  MSExchangeService... EWS.Proxy       Unhealthy  EwsProxy
Server        Offline         OutlookMapiHttpPr... MSExchangeMapiFro... OutlookMapiH... Unhealthy  MapiProxy
Server        Offline         OABProxyTestMonitor  MSExchangeOABAppPool OAB.Proxy       Unhealthy  OabProxy
Server        Offline         OutlookProxyTestM... MSExchangeRpcProx... Outlook.Proxy   Unhealthy  RpcProxy
Server        NotApplicable   EWSDeepTestMonitor   Mailbox Database ... EWS.Protocol    Unhealthy  None
Server        NotApplicable   EWSSelfTestMonitor   MSExchangeService... EWS.Protocol    Unhealthy  None
Server        NotApplicable   EdiscoveryDeepTes...                      Ediscovery.P... Unhealthy  None
Server        NotApplicable   EWSCtpMonitor        Server.USD108.l... EWS             Unhealthy  None
Server        NotApplicable   MaintenanceFailur...                      ECP             Unhealthy  None
Server        NotApplicable   MaintenanceFailur...                      FEP             Unhealthy  None
Server        NotApplicable   MaintenanceFailur...                      OWA             Unhealthy  None
Server        NotApplicable   DatabaseHealthCir... Mailbox Database ... DataProtection  Unhealthy  None
Server        Online          OnPremisesSmtpCli...                      FrontendTran... Unhealthy  Fronten...
Server        Online          MessageCountMonitor  Transport            Transport       Disabled   HubTran...
Server        NotApplicable   RpsCtpPSMonitor                           RPS             Unhealthy  None
Server        Online          DeferredMessageCo... Transport            Transport       Disabled   HubTran...
Server        NotApplicable   RpsDeepTestPSProx...                      RPS             Unhealthy  None
Server        Online          AverageMessageCou... Transport            Transport       Disabled   HubTran...
Server        Online          TotalMessageCount... Transport            Transport       Disabled   HubTran...
Server        NotApplicable   OutlookRpcDeepTes...                      Outlook.Prot... Unhealthy  None
Server        Offline         UMCallRouterTestM...                      UM.CallRouter   Unhealthy  UMCallR...
Server        Online          MessageCountExcee... Transport            Transport       Disabled   HubTran...
Server        Online          MessageCountExcee... Transport            Transport       Disabled   HubTran...
Server        NotApplicable   ComplianceOutlook...                      Compliance      Unhealthy  None
Server        NotApplicable   OutlookRpcCtpMonitor                      Outlook         Unhealthy  None
Server        NotApplicable   PassiveDatabaseAv... Mailbox Database ... Store           Disabled   None
Server        Online          AggregatedQueueMo...                      Transport       Disabled   HubTran...
Server        NotApplicable   SearchMemoryOverT...                      Search          Disabled   None
Server        NotApplicable   MailboxDeliveryAv...                      MailboxTrans... Unhealthy  None
Server        Online          Transport.NDRForU... HubTransport         HubTransport    Disabled   HubTran...
Server        Online          TransportLogGener...                      HubTransport    Disabled   HubTran...
Server        Online          TransportCategori...                      HubTransport    Disabled   HubTran...
Server        Online          FederatedDecrypti...                      HubTransport    Disabled   HubTran...
Server        Online          TransportDelivery...                      HubTransport    Disabled   HubTran...
Server        Online          TransportDelivery...                      HubTransport    Disabled   HubTran...
Server        NotApplicable   TransportDelivery...                      MailboxTrans... Disabled   None
Server        Online          IsMemberOfResolve...                      HubTransport    Disabled   HubTran...
Server        Online          IsMemberOfResolve...                      HubTransport    Disabled   HubTran...
Server        Online          Transport.DomainS... HubTransport         HubTransport    Disabled   HubTran...
Server        Online          Transport.DomainS... HubTransport         HubTransport    Disabled   HubTran...
Server        Online          TlsDomainClientCe... HubTransport         HubTransport    Disabled   HubTran...
Server        Online          Transport.DomainS... HubTransport         HubTransport    Disabled   HubTran...
Server        Online          Transport.DomainS... HubTransport         HubTransport    Disabled   HubTran...
Server        NotApplicable   TransportFedCertM... MSExchangeCertifi... MSExchangeCe... Disabled   None
Server        NotApplicable   TransportFedCertE... MSExchangeCertifi... MSExchangeCe... Disabled   None