Sender address verification rejecting mail

Hi experts, hoping for some assistance with this;
We have implemented a new SBS2011 server which appears to be unable to deliver mail to any remote server that uses sender address verification.
When I test using telnet from our server to one of the remote servers giving us trouble I get the following:

220 remote.safenetbox.biz ESMTP NetBox(tm)
ehlo mx.mydomain.com.au
250-remote.safenetbox.biz
250-PIPELINING
250-SIZE 100000000
250-VRFY
250-ETRN
250-STARTTLS
250-ENHANCEDSTATUSCODES
250-8BITMIME
250 DSN
mail from:me@mydomain.com.au
250 2.1.0 Ok
rcpt to:recipient@remotedomain.com.au
450 4.1.7 <me@mydomain.com.au>: Sender address rejected: unverifi
ed address: lost connection with mx.mydomain.com.au[203.45.203.251] wh
ile sending RCPT TO

The mailfrom address is a legitimate address which I can send email to.  There were some dns issues previously with the ptr and mx records however I can now verify the primary mx, ptr and smtp banner all match.  At first glance it would appear to me that when the remote server does an rcpt to test on the sender address it fails, but why?  
The setup is very simple; a virtualised SBS2011 machine sitting behind NAT; the primary mx is the WAN IP and we are not using a smart host to deliver mail.  Appreciate any assistance.
LVL 6
CorpCompAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Manpreet SIngh KhatraSolutions Architect, Project LeadCommented:
SO your MX is pointing to your Firewall\Gateway server .... are you able to send email to Public domain ?

Check with your Domain blacklist
www.mxtoolbox.xom

- Rancy
upul007Commented:
Hi,

You should also set up SPF records. See  http://www.kitterman.com/spf/validate.html and http://www.openspf.org/ for more info on SPF.

Seems the connection from the other domain is being reset by your domain. It does not allow the query to be passed. Is there any type of restrictions on what kind of traffic is allowed through to your server? and also is there a firewall?
CorpCompAuthor Commented:
Thanks for the responses guys.  Yes the mx is pointing to the gateway, and I can send mail to the public domain without issue.  MXtoolbox doesn't show the server as being on any blacklist.  Unfortunately as we currently don't yet have full control over DNS for this domain we're unable to implement SPF records at this time.
The server is sitting behind a NAT firewall and port 25 is forwarded, no other firewall is in use.  
One thing I did notice is that every domain we can't send to appears to be using a netbox blue utm appliance.
Making Bulk Changes to Active Directory

Watch this video to see how easy it is to make mass changes to Active Directory from an external text file without using complicated scripts.

Manpreet SIngh KhatraSolutions Architect, Project LeadCommented:
Try with Inbound email from below URL
www.exrca.com

Ask them to check if they need to whitelist your IP or something ?

- Rancy
CorpCompAuthor Commented:
The inbound smtp mail flow test has passed; I'm still waiting on a reply from the sysadmin at the remote site since we rectified the dns records.
Manpreet SIngh KhatraSolutions Architect, Project LeadCommented:
If DNS has been changed across sites it will wait for the interval :)
If SMTP test passed than it should work fine .... just try to telnet from Internet machine and see if you can drop an email.

- Rancy

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
CorpCompAuthor Commented:
Hmmm...  Rancy it seems you may have been right.  I just did another telnet test from our server to the problem domain and now receive a 250 2.1.0 Ok after the rcpt to command.  Although the DNS records were changed late last week it seems I was still being a bit impatient.  Not sure yet whether or not the email has arrived safely in the recipients inbox but will let you know.
Manpreet SIngh KhatraSolutions Architect, Project LeadCommented:
Sure will wait for your update :) ..... if anything will be here :)

- Rancy
CorpCompAuthor Commented:
Well it seems it was just a matter of waiting for the remote server to update it's DNS...  all seems to be working now. Thanks for your help :)
Manpreet SIngh KhatraSolutions Architect, Project LeadCommented:
There you go whenever you make changes to MX or PTR on the ISP DNS it takes time to update with all Internet DNS servers ... so i always go for weekend as the IMPACT is least :)

- Rancy
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Microsoft Server OS

From novice to tech pro — start learning today.