nativespace-sun.ns-sun.com #550-"JunkMail rejected

Your best bet is to make sure that your firewall is blocking all SMTP (TCP Port 25) traffic outbound except from your mailserver.
If you are on CBL - it is likely that you are sending out spam - which could be as a result of authenticated relaying.
http://www.mxtoolbox.com/blacklists.aspx is a site you can check to see if you are on blacklists - not sure if you checked this site to see if you are listed, but it is a good place to check more than one blacklist.
You can check your reputation on http://www.senderbase.org/ which again, you may have checked.
Have you downloaded and installed Malwarebytes (www.malwarebytes.org) as this tool can detect items that your Anti-Virus program cannot locate.
Have a read through the following EE question (refer to Xmachne's advice) to give general advice about searching for problems on your network:
https://www.experts-exchange.com/questions/24463550/How-to-identify-which-machine-is-infected-and-sending-Spam-which-keeps-getting-me-blacklisted.html?cid=238&anchorAnswerId=24606079#a24606079 

<Your best bet is to make sure that your firewall is blocking all SMTP (TCP Port 25) traffic outbound except from your mailserver.>

My firewall is blocking all smtp (port 25) traffic outbound except my exchange server.

<http://www.mxtoolbox.com/blacklists.aspx is a site you can check to see if you are on blacklists - not sure if you checked this site to see if you are listed, but it is a good place to check more than one blacklist.>

I`ve checked there and it was blacklisted. I removed it from black list.

<You can check your reputation on http://www.senderbase.org/ which again, you may have checked.>

I checked it also and my reputation is poor but it is poor only recently. I think that that is because my IP was blacklisted for a past few days.

<Have you downloaded and installed Malwarebytes (www.malwarebytes.org) as this tool can detect items that your Anti-Virus program cannot locate.>

Yes, I`ve installed few antispy/ antimalware software (XoftSpy, SpyBoot, Microsoft MSRT (Malicious Software Removal Tool) and Malwarebytes) and they haven`t found infected objects. My exchange server is clean.

I suspect that problem is in this:
"I have analyze problem and saw that we were listed in CBL late at night when we recived mail from our client externalclient2@externaldomain2.com.

This mail was sent to our mail-enabled Universal group in which there was an another external mail contact from our exchange server (externalcontact@externaldomain3.com). "

Practically, my mail server routing mail from externalclient2@externaldomain2.com to contact at my exchange server (externalcontact@externaldomain3.com). It`s confusing because my mail server do it all the time. My wild guess is because the externaldomain2.com have poor reputation look up. But maybe I am wrong.

Can you help mi with this, it's confusing.

Can you email me the specific details (details in my profile) as it is going to be difficult to resolve this without being able to research the problem myself and understand what the exact problem is.
Thanks
Alan

Because of the company policies I can give you only this:

Delivery has failed to these recipients or distribution lists:
externaluser1@externaldomain.co.uk
An error occurred while trying to deliver this message to the recipient's e-mail address. Microsoft Exchange will not try to redeliver this message for you. Please try resending this message, or provide the following diagnostic text to your system administrator.
The following organization rejected your message: nativespace-sun.ns-sun.com.
________________________________________
Sent by Microsoft Exchange Server 2007

Diagnostic information for administrators:
Generating server: exchsrv.MYCOMPANY.LOCAL
externaluser1@externaldomain.co.uk
nativespace-sun.ns-sun.com #550-"JunkMail rejected - mail.mycompany.rs (mail.mycompany.co.rs) 550-[89.216.xxx.xx]:2538 is in an RBL, see 550 http://www.spamhaus.org/query/bl?ip=89.216.xxx.xx" ##

These are the facts:

I`ve checked that :
1. our mail server is not open relay
2. our mail server have spam and antivirus protection
3. I checked our mail server and it doesn't have spam/virus trojans
4. our external IP is a firewall/gateway IP, and firewall is configured to prevent outbound port 25 connections to the Internet except from my mail server (exchange 2007)

I haven`t got any problems until a few days ago when I've got first mail from the mail address externalclient2@externaldomain2.com. I suspect that problem is with relay of that mail to the mail contact at my exchange server (externalcontact@externaldomain3.com). Can it be the problem??? Again, I checked for Openrelay Check at the http://www.dnsgoodies.com/ and my mail server does not allow open relay.

I checked every other solution which is associated with spam/malware/trojans virus.

That is all I can say. Thanks for your trouble.

Ivan

I`ve checked that :
1. our mail server is not open relay - Good
2. our mail server have spam and antivirus protection - Good
3. I checked our mail server and it doesn't have spam/virus trojans - Good
4. our external IP is a firewall/gateway IP, and firewall is configured to prevent outbound port 25 connections to the Internet except from my mail server (exchange 2007) - Good
I haven`t got any problems until a few days ago when I've got first mail from the mail address externalclient2@externaldomain2.com. I suspect that problem is with relay of that mail to the mail contact at my exchange server (externalcontact@externaldomain3.com). Can it be the problem??? - Are you auto-forwarding emails to externalcontact@externaldomain3.com?  If you are, this is extremely unlikely to be causing you problems if the messages you receive are genuine and externalcontact@externaldomain3.com is a valid address.
What is more likely is that you are not an Open Relay, but an Authenticataed relay, i.e., someone is directly abusing your server and has a valid username and password and is sending mail out via your exchange server.
Do any of your users access your Exchange Server from outside the building?
Have you reset all your passwords for all accounts including the Administrator account?
Did you rename the administrator account when the server was installed - Administrator is the biggest target and renaming it will make it more difficult to abuse your server.
Have you checked your Email queues to see if there are lots of messages that are sitting around not going anywhere that originate from internal users?
 

Do any of your users access your Exchange Server from outside the building? - NO
Have you reset all your passwords for all accounts including the Administrator account? Our password complexity is very strong
Did you rename the administrator account when the server was installed - Administrator is the biggest target and renaming it will make it more difficult to abuse your server.  Yes, first thing after installation
Have you checked your Email queues to see if there are lots of messages that are sitting around not going anywhere that originate from internal users?  This is interesting, no unusual messages were in a Queue. There were only massages from inside our company and from our business contacts outside our domain. These are all trusted email addresses. That is confusing in this problem.

Maybe is problem with our ISP. Our ISP is ISP SERBIA-BROADBAND and it is blacklisted at UCEPROTECTL2 and UCEPROTECTL3.

UCEPROTECTL2: ISP SERBIA-BROADBAND-AS Serbia Broadband Autonomous System/AS31042 is UCEPROTECT-Level3 listed for hosting a total of 1099 abusers.
Return codes were: 127.0.0.2

UCEPROTECTL3: Net 89.216.0.0/16 is UCEPROTECT-Level2 listed because 430 abusers are hosted by SERBIA-BROADBAND-AS Serbia Broadband Autonomous System/AS31042 there.
Return codes were: 127.0.0.2

Or maybe problem is that I am authenticated relay??? But I doubt..

Thx.

Do you send your emails out via your ISP or directly via DNS?
If you send them via your ISP and they are blacklisted, then this is your problem - switch to DNS and you should be okay.
To check, open up Exchange System Manager and expand Connectors.  Right click your default SMTP connector and choose properties.  On the first screen you will see if you use your ISP (Smart Host) or DNS.

I send it via my DNS. Maybe problem is in the FQDN of my domain. FQDN for my exchange server is exchangeserver.mydomain.local   but my domain to outside world is mydomain.co.rs. Maybe I am blacklisted because they expected mydomain.co.rs and they get mydomain.local and they dont know what .local is?? But this wasnt a problem until now..

Your FQDN should be set to the same as your MX record, so please go ahead and change it.
It will not necessarily be causing you the problems, but it is best practise, so is a good move.
It would be extremely useful to get specific about your domain so that I can run some external tests on your domain and IP address and check the results myself.  I understand your company policy, but it is difficult to assist without being able to see the full picture.

Is this email valid alan@it-eye.co.uk ?