There is likely a restriction on the mail server which is preventing you from relaying from your SharePoint servers to your mail server (e.g. they have added specific allowed IPs in a receive connector).
You can test this in two ways:
Send-MailMessage
This will use Windows PowerShell to test email. Make sure to run this on your SharePoint server. Alternatively, you can use the SharePoint Management Shell to run the below which will test email flowing from the SharePoint object model using your Central Admin outgoing email settings.
$email = "[email protected]"
$subject = "Email through SharePoint OM"
$body = "Message body."
$site = $null
if ($site -eq $null)
{
$site = (Get-SPWebApplication -IncludeCentralAdministration | ?{$_.IsAdministrationWebApplication -eq $true}).Url
}
$site = Get-SPSite $site
$web = $site.OpenWeb()
[Microsoft.SharePoint.Utilities.SPUtility]::SendEmail($web,0,0,$email,$subject,$body)
Write-Host "If the result returns True, the email has been sent to the SMTP server successfully."