General Office 365 email setup check list:
  1. MS requires that each smart-host configuration or send connector setting must use only the assigned host record (e.g. domain-com12345.mail.protection.outlook.com)
    – Verify this record at: https://admin.microsoft.com/AdminPortal/Home#/Domains
  2. TXT record should be inclusive of certain relaying subnets:
    – Example:  Text: v=spf1 mx a ip4:x.x.x.x/30 include:spf.protection.outlook.com include:spf.ess.barracudanetworks.com ~all
    – This helps with spam filtering, rather than email routing.
  3. Third-party filtering service should be routing to the correct smart-host record as shown in (a). For instance, barracudanetworks should route to the correct smtp server as ‘domain-com12345.mail.protection.outlook.com’
  4. Check the connection filtering with access privileges using a Global Admin account at URL
  5. Authenticate to Office.com using a Global Admin account > Navigate to Exchange Admin Center (Admin > Exchange) > Mail flow > Connectors > Check the list of connectors set up for your organization. If there are no connectors listed from your organization’s email server to Office 365, create one by clicking on the ‘+’ sign >
    Set From = Public IP address of the Email Relaying Computer, Set To = Office 365 > Next > Next > Save
    # Preempt this email relaying error:

    Error in processing. The server response was: 4.4.62 Mail sent to the wrong Office 365 region. ATTR35. For more
    information please go to https://learn.microsoft.com/en-us/exchange/troubleshoot/email-delivery/wrong-office-365-region-exo
    [BN8NAM12FT036.eop-nam12.prod.protection.outlook.com]
Sample DNS Records:
----------------------------
CNAME: autodiscover autodiscover.outlook.com 5 minutes (300 seconds)
CNAME: sip sipdir.online.lync.com 5 minutes
CNAME: lyncdiscover webdir.online.lync.com 5 minutes
CNAME: enterpriseregistration enterpriseregistration.windows.net 5 minutes
CNAME: enterpriseenrollment enterpriseenrollment-s.manage.microsoft.com 5 minutes
TXT: @ v=spf1 include:spf.protection.outlook.com -all 5 minutes
SRV: _sip._tls.@ 100 1 443 sipdir.online.lync.com 5 minutes
SRV: _sipfederationtls._tcp.@ 100 1 5061 sipfed.online.lync.com 5 minutes
MX: <MX-prefix>.mail.protection.outlook.com 5 minutes (Obtain MX-prefix from: https://admin.microsoft.com/AdminPortal/Home#/Domains)
CNAME: imap outlook.office365.com
CNAME: mail outlook.office365.com
CNAME: pop outlook.office365.com
CNAME: smtp smtp.office365.com
----------------------------
# Quick DNS checkup:
nslookup -type=a autodiscover.domain.com
nslookup -type=cname autodiscover.domain.com
nslookup -type=a mail.domain.com 8.8.8.8
nslookup -type=cname mail.domain.com
nslookup -type=mx domain.com 8.8.8.8
nslookup -type=txt domain.com 8.8.8.8
nslookup -type=srv _sip._tls.domain.com 8.8.8.8
nslookup -type=srv _sipfederationtls._tcp.domain.com 8.8.8.8

A convenient PowerShell function to perform this lookup:

function checkMailRecord{
	param(
		$domainName='google.com',
		$dnsServer='8.8.8.8'
	)
	$autodiscover=(Resolve-DnsName "autodiscover.$domainName" -type CNAME -server $dnsServer).NameHost
	$mx=(Resolve-DnsName $domainName -type MX -server $dnsServer|?{$_.Section -eq 'Answer'}).NameExchange
	$text=(Resolve-DnsName $domainName -type TXT -server $dnsServer|?{$_.Strings -like 'v=spf1*'}).Strings
	$sip=(Resolve-DnsName "_sip._tls.$domainName" -Type SRV -server $dnsServer|?{$_.Section -eq 'Answer'}).NameTarget
	$sipFederation=(Resolve-DnsName "_sipfederationtls._tcp.$domainName" -Type SRV -server $dnsServer|?{$_.Section -eq 'Answer'}).NameTarget
    write-host "
    AutoDiscover: $autodiscover
    Mail Exchange (MX): $mx
    Text: $text
    SIP: $sip
    SIP Federation: $sipFederation
    "    
}

checkMailRecord kimconnect.com

# Sample output
PS C:\users\test> checkMailRecord kimconnect.com                                                 
    AutoDiscover: autodiscover.outlook.com
    Mail Exchange (MX): kimconnect-com.mail.protection.outlook.com
    Text: v=spf1 ip4:x.x.x.x/30 include:spf.protection.outlook.com ~all
    SIP: sipdir.online.lync.com
    SIP Federation: sipfed.online.lync.com