Exchange. Not receiving external mail...

Have you created with your External DNS server for your domain to see if you have created the appropriate A, and MX records.  Have you also called your ISP who is hosting your Internet Access to request a PTR record created for your WAN IP address to point to the domain you have, ie) mail.yourdomain.com

So when servers do a reverse lookup of your IP that it resolves to the correct hostname?

If you try and send to a domain that has an RBL check or SPAM blocker and it does a reverse DNS lookup for your IP and you dont have a PTR record set up for your WAN IP with your ISP, its most likely going to block your message as probable SPAM

Have you tried sending a message via the command line using telnet on your mail server.
ie)

C:>telnet problemdomain.com 25
     ehlo mydomain.com
     mail from:user@yourdomain.com
     rcpt to:user@problemdomain.com
     Data
     Subject:Test

     This is a test message.
     .
     Quit

See if you get any error that way from your server just to see if anything fishy and get any kind of error messages like RBL blacklist, or blocked???

ok, some external mail is coming in, for instance I got the notification mail from expertsexchange to say there was a comment added to my question. So only some mail is bouncing back, 3 users have reported it this afternoon...

What are the bounced messages reporting as the error?  If you could copy and paste the relevant details that'd be a great help.

Also, not having any known issues sending mail externally...
Sending and receiving mail internally fine.

unknown address error
5.1.0 550 error

Your just having trouble then receiving mail from the outside world correct?

Ok, need a bit more info than that... what server is reporting that error?  Is it your Exchange server that generated it?  Or does your email come via an ISP?

The error report should have full SMTP error including reporting server (change any details you don't want public).

where did you see error?

ok

Sent one from hotmail earlier and heres what came back to it:

Reporting-MTA: dns;bay0-omc3-s22.bay0.hotmail.com
Received-From-MTA: dns;BLU116-W9
Arrival-Date: Thu, 4 Oct 2007 08:20:52 -0700

Final-Recipient: rfc822; myname@ourdomain.com
Action: failed
Status: 5.7.1
Diagnostic-Code: smtp;550 5.7.1 Requested action not taken: message refused

its just from the outside world yes NoodlesWIU

just sent one from a gmail account and it came through...?

Have you double checked your external DNS records to make sure they are pointing to the correct IP Address.  ie A record, and MX record

550 5.7.1 is an unable to relay error.  I still can't see which server is actually generating that error though.

How is the mail delivered into your Exchange server?  Is it directly (i.e. MX records point straight to it), or collected/forwarded from ISP?  Is there anything else that the mail goes through before reaching Exchange (e.g. spam filter, ISA server)?

http://support.microsoft.com/kb/895857

There are various causes (mainly firewalls) listed there.  Do any of these apply to you?

Hardware firewall on netgear router which forwards smtp traffic to exchange server, havent changed anything on this recently.

Symantec mail security for MS Exchange on exchange server but I dont think this is the issue as some mail not reaching box it would seem...

Just ran test on dnsstuff again and this time its showing this error aswell as previous ones:

ERROR: I could not complete a connection to one or more of your mailservers:
ERROR: mxbackup.iol.net Greeting indicates server is down: 421 Too many concurrent SMTP connections; please try again later. .<br />mxbackup.iol.net: The mailserver terminated the connection before the transaction was complete

Diagnostic-Code: smtp;550 5.7.1 Requested action not taken: message refused

There is usually a report of which mail server gave this error.  While you may not wish to post the actual server, is it your Exchange server that generated it or another server?

purple
Diagnostic-Code: smtp;550 5.7.1 Requested action not taken: message refused

this NDR comes from postmaster@mail.hotmail.com

rest of the stuff in the NDR I've posted exactly just with domain name changed

Some reports don't include it... I guess Hotmail doesn't.  Shame, it can greatly help track down the source of the problem.

If you look in message tracking on the Exchange server, is there a log for the message that was refused?  Or is there nothing there at all?

Ya I've looked there. Some external mail is there for the user but the mail from the external sender reporting the NDR isnt of course. Seems to fit the test pattern I had I suppose of mail from gmail delivering fine but mail from hotmail being refused, strange.

Ya checked the Symantec Mail Security logs and nothing there. External mail is coming in this morning aswell (I've just got a mail from hotmail which was bounced yesterday). Looks like another server so...will see how it pans out for the day..

Was coming from an external server, all is well now.