Relaying denied. Blacklist Removal?

If you are blacklisted you neeed to know why you are blacklisted and get off them, but only after sorting out why you were on them in the first place.
What is your IP Address (I will obscure it after posting).  I can check and see if I can see why you are listed.
Alan

first see where you are blacklisted, the ISP is sometimes the source depending on what checks the receiving server does.
enter you ip\dns name here  

http://www.mxtoolbox.com/blacklists.aspx

are you blacklisted and if so on what level?
next try

http://www.blacklistalert.org./
 and comment back with results..

Gilad

IP Address: 210.54.xxx.xxx

Results from Blacklist Alert::

0spam.fusionzero.com OK
aspews.ext.sorbs.net OK
bl.spamcop.net OK
bl.spamcannibal.org OK
blackholes.five-ten-sg.com OK
blackholes.intersil.net OK
bogons.cymru.com OK
cbl.abuseat.org OK
combined.njabl.org OK
db.wpbl.info OK
dnsbl.ahbl.org OK
dnsbl.inps.de OK
dnsbl.sorbs.net OK
dnsbl.rangers.eu.org OK
dnsbl-0.uceprotect.net OK
dnsbl-1.uceprotect.net OK
dnsbl-2.uceprotect.net OK
dnsbl-3.uceprotect.net OK
dyna.spamrats.com OK
ips.backscatterer.org OK
ix.dnsbl.manitu.net OK
l2.apews.org OK
no-more-funn.moensted.dk OK
noptr.spamrats.com OK
psbl.surriel.com OK
rbl.efnet.org OK
spam.spamrats.com OK
spamguard.leadmon.net OK
t1.dnsbl.net.au OK
tor.dan.me.uk OK
tor.dnsbl.sectoor.de OK
ubl.unsubscore.com OK
virbl.dnsbl.bit.nl OK
zen.spamhaus.org OK

--------------------------------------------------------------------------------
Result in LHSBL Whitelists (Alphabetic order):

ips.whitelisted.org NOT WHITELISTED Read about this way to exclude an IP from UCEPROTECT Level2/3
list.dnswl.org NOT WHITELISTED

--------------------------------------------------------------------------------

abuse.rfc-ignorant.org OK
bogusmx.rfc-ignorant.org OK
dsn.rfc-ignorant.org OK
dynamic.rhs.mailpolice.com OK
l1.apews.org OK
list.anonwhois.net OK
multi.surbl.org OK
multi.uribl.com OK
postmaster.rfc-ignorant.org OK
rddn.dnsbl.net.au OK
rhsbl.ahbl.org OK
rhsbl.sorbs.net OK
webmail.rhs.mailpolice.com OK

so you are not blacklisted.

is this a new mail server setup? was the blacklist error sudden? what is your configuration and what server is it?

When running the blacklist check from MX Toolbox it tells me that we are blacklisted. i.e:
ICMFORBIDDEN  LISTED Return codes were: 127.0.0.50 82723 1373

No, this isn't a new server setup. We are running Exchange 2003 on a Server 2003 box.

Not seen that Blacklist before.  Lots of suggestions that you are an open relay in the lick on the blacklist site (mxtoolbox).
Checking on www.checkor.com shows you are not an open relay.
How is your DNS configured on your server?  What is your Servers DNS 1 / 2 record and are you using DNS Forwarders on your DNS server?

try to do this:

open a command line (start-->run-->cmd)

type :
NSLOOKUP
set type=mx
domain.com(your domain)
you should get a result, try to do
telnet "result of nslookup" 25
what did you get?

thanks for the advice so far. I've changed the SMTP Virtual Server FQDN to smtp.mydomain. This should now make 2 of those matching.

Cricket is actually a website on our domain. After you mentioning that I had a look at our dns records, I notice our IP address has multiple A Records. Is this why it might be getting confused? Should there only be 1 A Record, and the rest should be CNAME (aliases)?

I keep getting a different result for Reverse DNS when running a check to the IP. is that normal?
Also, I still have a problem with being on the ICMFORBIDDEN blacklist. I've gone to the site but it doesn't give me much help.

alanhardisty is right, blacklist checks are made also on reverse dns..
you should have only one pointing to you real server (same as mx record 100)

It may also be worth having a read of the following article for clarification:
https://www.experts-exchange.com/Software/Server_Software/Email_Servers/Exchange/A_2370-Exchange-DNS-Configuration.html 

thanks for all your help.
I've now changed our Reverse DNS Records to only have smtp.mydomain. This should now mean all my records are consistent.

1. A record for smtp.mydomain
2. MX record for smtp.mydomain pointing to the A record
3. Exchange Virtual SMTP connector FQDN smtp.mydomain

Now, any ideas how to get off the ICMForbidden blacklist? When I go to the site http://sunsite.icm.edu.pl/spam/bh.html it doesn't help me at all.

You are looking much tidier now :)
Not got a clue how to get off the ICMFORBIDDEN site - it's Polish and I don't speak a word!
Sorry.

To make everything completely tidy, you might want to add an SPF record too.

This question has been classified as abandoned and is being closed as part of the Cleanup Program. See my comment at the end of the question for more details.