Exchange Server 2010 not recieving mail and bouncing back emails

Hi

I have read previous threads and can't seem to find the solution.

I am running an Exchange Server 2010 on a Server 2008 R2. I have a BT Broadband Connection with a firewalled router and my domain hosted with a hosting company.My Exchange Server was set up by an IT Consultant who I can't get hold of anymore. This is a new installation and no previous server existed.

I can send inbound mail but cannot recieve any mail. BT told me my router IP address which I gave to my domain hosting company who set up a pointer. I cannot recieve any mail now via pop email or exchange. Emails are being bounced back from apparantley my server. Snippet is below. I have run the Exchange Connectivity Tools and some errors come up which I dont know how to resolve. Please can someone give me a step by step fix guide as I am losing a lot of important emails.

Snippet:
Date: Tue, 28 Jun 2011 07:55:34 +0100
Subject: Mail Delivery Failure


This is the mail delivery agent at messagelabs.com.

I was unable to deliver your message to the following addresses:

User@domain.eu (I changed this myself but was my email address)

Reason: 550-mail1.bemta14.messagelabs.com [193.xxx.xxx.xx]:13337 is currently not
550-permitted to relay through this server. Perhaps you have not logged into
550-the pop/imap server in the last 30 minutes or do not have SMTP
550 Authentication turned on in your email client.

The message subject was: RE: Environmental Manager and Assistant Environmental Manager Roles
The message date was: Mon, 27 Jun 2011 11:33:34 +0100
The message identifier was: EC/20-20436-28C580E4
The message reference was: server-10.tower-72.messagelabs.com!1309170813!36736907!1

Please do not reply to this email as it is sent from an unattended mailbox.
Please visit www.messagelabs.com/support for more details
about this error message and instructions to resolve this issue.

Thanks in advance.

 

Love to help on this, but we are on exchange 2003. Though, soon we will be on exchange 2010 in about a month or so. I know this won't help, but sounds like perhaps a DNS issue.

So, from what you stated, internal mail works? Sending mail to the outside works? Sending mail from like gmail to your domain does not?

 

Hi, that is correct.

We can send email via exchange out of the organisation and also to each other from within the organisation. If anyone replies to the exchange email then they the getthe error message and we dont get the mail. I do get a delivery reciept though.

I have got pop accounts setup but this is not good as nothing runs through the exchange. What should DNS settings look like to allow flow of mail from Internet-Router-Firewall-MS Exchange-Client?

 

I believe it should be your external DNS, not sure who your provider is.

I know the following is for exchange 2007, but it might help:
http://demazter.wordpress.com/2010/02/09/exchange-dns-configuration/