O365 hybrid connector to onprem failing TLS

did you tried with rerun the hybride wizard on the server, this could solve the issue. 

I will reach out to a former colleague of me at Microsoft maybe he has some ideas.

here is an powershell script that may help, be care full it will change certain settings in the connector if you have modified it.

<#
.SYNOPSIS
  Diagnose (and optionally remediate) common STARTTLS issues on Exchange.

.DESCRIPTION
  - Validates SMTP certificate health & binding to receive connectors.
  - Confirms STARTTLS is advertised on ports 25/587 via EHLO probe.
  - Checks on-prem Send Connector to EXO and (optionally) EXO connectors.
  - Optional -FixTlsBinding will rebind Default Frontend receive connector
    to the active SMTP certificate and restart FrontEndTransport.

.NOTES
  Run in the on-prem Exchange Management Shell as Organization Management.
  For EXO checks, you need the ExchangeOnlineManagement module and a session
  via Connect-ExchangeOnline.

.PARAMETER ExchangeServer
  The on-prem Exchange server name (defaults to local).

.PARAMETER ExpectedCertNames
  CN/SAN values you expect on the SMTP cert (e.g., mail.contoso.com).

.PARAMETER PortsToTest
  Ports to EHLO probe for STARTTLS advertisement (defaults 25,587).

.PARAMETER CheckEXO
  Also check EXO inbound/outbound connectors (requires EXO connection).

.PARAMETER FixTlsBinding
  Rebind Default Frontend receive connector to the active SMTP cert.

.EXAMPLE
  .\Test-ExchangeStartTls.ps1 -ExpectedCertNames mail.contoso.com -CheckEXO

.EXAMPLE
  .\Test-ExchangeStartTls.ps1 -ExpectedCertNames mail.contoso.com -FixTlsBinding
#>

[CmdletBinding(SupportsShouldProcess)]
param(
  [string]$ExchangeServer = $env:COMPUTERNAME,
  [string[]]$ExpectedCertNames,
  [int[]]$PortsToTest = @(25,587),
  [switch]$CheckEXO,
  [switch]$FixTlsBinding
)

# --------- helpers ----------
$Report = New-Object System.Collections.Generic.List[object]
function Add-Row([string]$Area,[string]$Item,[string]$Status,[string]$Details,[string]$Recommendation="") {
  $Report.Add([pscustomobject]@{Area=$Area;Item=$Item;Status=$Status;Details=$Details;Recommendation=$Recommendation})
}
function OK   { "OK" }
function WARN { "WARN" }
function FAIL { "FAIL" }

function Test-EhloStartTls([string]$Host,[int]$Port){
  try{
    $client = New-Object System.Net.Sockets.TcpClient
    $client.ReceiveTimeout = 4000; $client.SendTimeout = 4000
    $client.Connect($Host,$Port)
    $stream = $client.GetStream()
    $reader = New-Object IO.StreamReader($stream)
    $writer = New-Object IO.StreamWriter($stream); $writer.AutoFlush = $true

    $banner = $reader.ReadLine()
    $writer.WriteLine("EHLO test.local")
    Start-Sleep -Milliseconds 100
    $lines = @()
    while ($stream.DataAvailable) { $lines += $reader.ReadLine() }
    $writer.WriteLine("QUIT")
    $client.Close()

    $hasStartTls = $lines -match "STARTTLS"
    [pscustomobject]@{
      Port        = $Port
      Banner      = $banner
      Lines       = ($lines -join "; ")
      HasSTARTTLS = [bool]$hasStartTls
    }
  } catch {
    [pscustomobject]@{ Port=$Port; Banner=$null; Lines=$_.Exception.Message; HasSTARTTLS=$false }
  }
}

Write-Host "== STARTTLS diagnostic on $ExchangeServer ==" -ForegroundColor Cyan

# 1) SMTP certificate posture
try{
  $smtpCerts = Get-ExchangeCertificate -Server $ExchangeServer | Where-Object { $_.Services -match 'SMTP' -and -not $_.IsSelfSigned }
  if(-not $smtpCerts){
    Add-Row "TLS/Cert" "SMTP certificate" (FAIL) "No third-party SMTP certificate enabled on $ExchangeServer" "Install a trusted SMTP cert and enable for SMTP."
  } else {
    foreach($c in $smtpCerts){
      $expired = ($c.NotAfter -lt (Get-Date))
      $nameHit = if($ExpectedCertNames){ @($c.CertificateDomains) | Where-Object { $ExpectedCertNames -contains $_ } } else { $true }
      $status  = if($expired){ FAIL } elseif($nameHit){ OK } else { WARN }
      $rec     = if($expired){ "Renew/replace and Enable-ExchangeCertificate -Services SMTP" }
                 elseif(-not $nameHit){ "Ensure EXO/on-prem connectors use a name present on this cert (CN/SAN)." } else { "No action." }
      Add-Row "TLS/Cert" "SMTP cert $($c.Thumbprint.Substring(0,8))" $status "Domains: $($c.CertificateDomains -join ', '); Expires: $($c.NotAfter)" $rec
    }
  }
} catch {
  Add-Row "TLS/Cert" "Query certificates" (FAIL) $_.Exception.Message "Run in Exchange Management Shell with proper rights."
}

# 2) Receive connectors (TLS binding + auth)
try{
  $rcvs = Get-ReceiveConnector -Server $ExchangeServer | Sort-Object -Property Name
  foreach($r in $rcvs){
    $isFrontend = $r.TransportRole -eq "FrontendTransport"
    $tlsName    = $r.TlsCertificateName
    $auth       = $r.AuthMechanism
    $hasTLS     = ($auth -match "Tls")
    $status     = if($hasTLS -and $isFrontend){ if([string]::IsNullOrWhiteSpace($tlsName)){ WARN } else { OK } } elseif($isFrontend){ WARN } else { OK }
    $rec        = @()
    if($isFrontend -and -not $hasTLS){ $rec += "Enable TLS in AuthMechanism for frontend receive connector." }
    if($isFrontend -and [string]::IsNullOrWhiteSpace($tlsName)){ $rec += "Bind TLS cert via Set-ReceiveConnector -TlsCertificateName '<I>issuer<S>subject'." }
    Add-Row "ReceiveConnector" $r.Identity $status "Auth: $auth; TlsCertificateName: $tlsName" ($rec -join " ")
  }
} catch {
  Add-Row "ReceiveConnector" "Query" (FAIL) $_.Exception.Message "Check permissions."
}

# 3) EHLO probe on 25/587 for STARTTLS
foreach($p in $PortsToTest){
  $probe = Test-EhloStartTls -Host $ExchangeServer -Port $p
  $status = if($probe.HasSTARTTLS){ OK } else { WARN }
  Add-Row "Probe" "EHLO $ExchangeServer:$($probe.Port)" $status "Banner: $($probe.Banner); EHLO: $($probe.Lines)" (if($status -eq "WARN"){"If missing on 25, fix TLS binding on Default Frontend."})
}

# 4) On-prem Send Connector toward EXO (if any)
try{
  $send = Get-SendConnector | Where-Object { $_.Name -like "Outbound to Office 365*" -or $_.TlsAuthLevel -ne 'None' }
  if($send){
    foreach($s in $send){
      $hosts = if($s.SmartHosts){ $s.SmartHosts -join "," } else { "DNS (no SmartHosts)" }
      $okTls = $s.RequireTLS -eq $true
      $okEop = ($hosts -match "mail\.protection\.outlook\.com")
      $status = if($okTls){ if($okEop -or $hosts -ne "DNS (no SmartHosts)") { OK } else { WARN } } else { WARN }
      $rec = @()
      if(-not $okTls){ $rec += "Set RequireTLS `$true` on the send connector." }
      if(-not $okEop){ $rec += "Point to EOP smart hosts (*.mail.protection.outlook.com) or per your design." }
      Add-Row "SendConnector" $s.Name $status "RequireTLS: $($s.RequireTLS); SmartHosts: $hosts; Fqdn: $($s.Fqdn)" ($rec -join " ")
    }
  } else {
    Add-Row "SendConnector" "Outbound to EXO" (WARN) "No TLS-enabled EXO send connector detected" "Re-run HCW to recreate it."
  }
} catch {
  Add-Row "SendConnector" "Query" (FAIL) $_.Exception.Message "Re-run HCW if needed."
}

# 5) Exchange Online connectors (optional)
if($CheckEXO){
  try{
    if(-not (Get-Command Get-InboundConnector -ErrorAction SilentlyContinue)){
      throw "Not connected to Exchange Online. Run Connect-ExchangeOnline first."
    }
    $inb = Get-InboundConnector
    foreach($i in $inb){
      $tlsOK = $i.RequireTls -eq $true -and $null -ne $i.TlsSenderCertificateName
      $intOK = $i.TreatMessagesAsInternal
      $status = if($tlsOK -and $intOK){ OK } else { WARN }
      $rec = @()
      if(-not $i.RequireTls){ $rec += "Set RequireTLS `$true` on EXO Inbound connector." }
      if(-not $i.TlsSenderCertificateName){ $rec += "Set TlsSenderCertificateName to your SMTP cert CN/SAN." }
      if(-not $intOK){ $rec += "Set TreatMessagesAsInternal `$true` for hybrid." }
      Add-Row "EXO" "InboundConnector '$($i.Name)'" $status "RequireTLS: $($i.RequireTls); TlsSenderCertificateName: $($i.TlsSenderCertificateName); Internal:$intOK" ($rec -join " ")
    }
    $outb = Get-OutboundConnector
    foreach($o in $outb){
      $status = if($o.RequireTls){ OK } else { WARN }
      Add-Row "EXO" "OutboundConnector '$($o.Name)'" $status "RequireTLS: $($o.RequireTls); Domains: $($o.RecipientDomains -join ',')" (if($status -eq "WARN"){"Set RequireTLS `$true`."})
    }
  } catch {
    Add-Row "EXO" "Connector checks" (WARN) $_.Exception.Message "Connect-ExchangeOnline and retry."
  }
}

# 6) Optional remediation: fix TLS binding on Default Frontend
if($FixTlsBinding){
  try{
    $active = Get-ExchangeCertificate -Server $ExchangeServer | Where-Object { $_.Services -match 'SMTP' -and -not $_.IsSelfSigned } | Sort-Object NotAfter -Descending | Select-Object -First 1
    if(-not $active){ throw "No suitable SMTP third-party certificate found." }
    $tlsName = "<I>$($active.Issuer)<S>$($active.Subject)"
    $def = Get-ReceiveConnector -Server $ExchangeServer | Where-Object { $_.Name -like "Default Frontend*" } | Select-Object -First 1
    if(-not $def){ throw "Default Frontend receive connector not found on $ExchangeServer." }

    if($PSCmdlet.ShouldProcess($def.Identity, "Bind TLS certificate $($active.Thumbprint.Substring(0,8))")){
      Set-ReceiveConnector $def.Identity -TlsCertificateName $tlsName
      Restart-Service MSExchangeFrontEndTransport -ErrorAction Stop
      Add-Row "Remediation" "Bind TLS to Default Frontend" (OK) "Set -TlsCertificateName and restarted FrontEndTransport" "Re-probe port 25 for STARTTLS."
    }
  } catch {
    Add-Row "Remediation" "Bind TLS to Default Frontend" (FAIL) $_.Exception.Message "Check cert/services and permissions."
  }
}

# Output
$Report | Sort-Object Area,Item | Format-Table -AutoSize
$Report

common causes for STARTTLS errors

 1. Missing or Incorrect TLS Certificate Binding

• After renewing an SMTP certificate, the Receive Connector may still reference the old certificate in its TlsCertificateName property.
• If the connector isn’t bound to a valid certificate, Exchange won’t advertise STARTTLS.

✅ 2. Self-Signed or Untrusted Certificate

• If the certificate used for SMTP isn’t trusted by the sending system (or is self-signed), STARTTLS negotiation can fail.

✅ 3. STARTTLS Disabled on Receive Connector

• The connector might have AuthMechanism settings that don’t include TLS, or RequireTLS is misconfigured.

✅ 4. Inline Devices Stripping STARTTLS

• Firewalls, load balancers, or SMTP appliances can remove the STARTTLS capability from the SMTP banner.

✅ 5. DNS or FQDN Mismatch

• The FQDN advertised by the connector doesn’t match the certificate CN/SAN, causing TLS handshake failures.

✅ 6. Outbound Connector Misconfiguration

• On-prem or Exchange Online connectors not set to RequireTLS or missing TlsSenderCertificateName.

✅ 7. Expired Certificate

• If the SMTP certificate is expired, STARTTLS will fail.

✅ 8. Opportunistic TLS Disabled

• If the sending system doesn’t attempt STARTTLS and the receiving system requires it, the message will be rejected.