Check if it's SBG or Externaldomain:
Look up the hostname of one ExternalDomain.com's MX records.
Login to the command line interface for your edge scanner.
Use telnet to simulate a mail connection to ExternalDomain.com
telnet mx_hostname.externaldomain.com 25
helo yourdomain.com
you should get a greeting
mail from: <you@yourdomain.com>
you should get an OK
rcpt to: <y@Externaldomain.com>
you should get an OK response
quit
If you get an error after any of these commands like the 554 transaction failed spam message not queued, then it's your IP that has a bad reputation.
You should then contact them via other means to work out the issue.