So the remote party is requiring TLS on outbound connections to YOUR MTA. Do you have a publicly signed certificate assigned to your Scanner? (e.g. signed by VeriSign?)
Per help for scanner setup:
Accept TLS encryption: Indicates whether to accept TLS-encrypted connections. You must configure an MTA TLS certificate and assign it to this Scanner before you can accept TLS encryption.
If you send me your domain (via private message) I'll use the openSSL tool on my scanner to validate your setup.
If you have a 2nd scanner you can try it yourself:
enable support account
login as support
issue the command
openssl s_client -connect <IP address>:25 -crlf -CAfile /usr/share/ssl/certs/ca-bundle.crt -starttls smtp
...where <IP address>is the IP address of the appliance with TLS encryption to be tested.