Before checking those hardware/software configs, are you sure your outgoing IP has a proper reverse DNS entry to begin with?
If not, it doesn't matter what you configure, it will always fail.
If not, check with your ISP to fix the reverse DNS entry.

The only entry that matters is the FQDN on the Send Connector, IF Exchange sends directly to the internet. If it is sending via your appliance, then it comes down to how the appliance is configured.

You cannot eliminate the .local from all headers, because Exchange moves the email internally. However that should not cause a problem with email flow and email being rejected - they are just looking at the initial connection.

Simon.

@Kimputer

The external static IP on our firewall is xx.xx.xx.xx which resolves to mail.ourdomain.co

and mail.ourdomain.co resolves to xx.xx.xx.xx

this comes from our ISP dns servers (checked from mxtools)

Then, as advised by Simon, you should indeed look at the FQDN string:

https://technet.microsoft.com/en-us/library/bb629503(v=exchg.141).aspx

Do you have a copy of such rejected email?
Hide the sensitive information and post the content of such rejection.

Sudeep

@Sudeep

mailrelay5.nv.gov rejected your message to the following e-mail addresses:

nevadaolt@tax.state.nv.us (nevadaolt@tax.state.nv.us)
mailrelay5.nv.gov gave this error:
Sender IP reverse lookup rejected

A problem occurred during the delivery of this message to this e-mail address. Try sending this message again. If the problem continues, please contact your helpdesk.

Diagnostic information for administrators:

Generating server: our_email_server.our_domain.local

nevadaolt@tax.state.nv.us
mailrelay5.nv.gov #550 Sender IP reverse lookup rejected ##

Original message headers:

Received: from our_email_server.our_domain.local ([::1]) by
 our_email_server.our_domain.local ([::1]) with mapi id 14.03.0279.002; Wed, 20
 Apr 2016 07:43:14 -0700
From: My Name <my email address>
To: "nevadaolt@tax.state.nv.us" <nevadaolt@tax.state.nv.us>
Subject: Test
Thread-Topic: Test
Thread-Index: AQHRmxL3wbIxcxkoT0e8TTsZfqnB2A==
Date: Wed, 20 Apr 2016 14:43:13 +0000
Message-ID: <D5B7FCAA-D87F-4200-9FEA-2C0B504EB95A@wirc.co>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/f.15.1.160411
x-originating-ip: [192.168.1.56]
x-exclaimer-md-config: d50af1dc-6ab8-492a-bb43-3dd2988cbab0
Content-Type: multipart/related;
      boundary="_007_D5B7FCAAD87F42009FEA2C0B504EB95Awircco_";
      type="multipart/alternative"
MIME-Version: 1.0

@Kimputer,

There is only one send connector and it is defined as follows:

General -> FQDN is mail.our_domain.co

Address Space -> SMTP * 1

Network-> Use DNS MX records to route mail automatically

Source Server-> our_email_server.our_domain.local

Do a test as I have outlined here:
http://blog.sembee.co.uk/post/Exchange-200720102013-Outbound-SMTP-Banner-Testing

That will confirm exactly how the internet sees your server.

Simon.

@Simon,

emmex.spamhaus.org gave this error:
*** The HELO for IP address xx.xx.xx.xx was 'mail.our_domain.co' (valid syntax) ***