550 Relay not permitted

Hi All,
I have a problem with one of our customers. We installed an exchange server at his premises last year and so far sending / receiving email has been fine.
A few days ago our customer started getting the following error when sending or replying to email from our company.

email@emailaddress.com on 28/01/2008 09:38
There was a smtp communication problem with the recipents email server.
Please contact your system administrator.
<server.domain.int # 5.5.0 smtp;550 relay not permitted>

At this stage i am trying to discover if this is a problem with our customers exchange server or is it a problem with our excahnge server? We do not have any block lists setup and i am told my customer can email other companies without any real problem, however i am also informed this problem is experienced with a hand full of other email addresses.

Any help on this would be very helpful

Thank you
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Mark DamenERP System ManagerCommented:
Have you changed their ISP?  and also how is the server configured for sending email, does it route all messages itself using DNS or does it forward to the ISP outgoing mail server through a smart host?

This message can appear if you use say BT for your internet connection, and then attempt to send email through AOL outgoing server.  hence why I asked the question whether they have change ISP or indeed whether the ISP they do use may have changed their outgoing server address?
...the previous expert's questions are appreciated!

Are you running any kind of filter on your mail such as the Intelligent Message FIlter from Microsoft?  If Yahoo is one of the domains the client's email system is having problems with there is a good chance that you just need a reverse DNS entry - been seeing a lot of this lately...pretty common these days for admins to have their servers perform a reverse DNS lookup.  Just make sure that if the mail server reports to be <some.server.com> then there should be a DNS entry for <some.server.com> with the IP for your server.

Mark DamenERP System ManagerCommented:
Any joy with our suggestions?
The Ultimate Tool Kit for Technolgy Solution Provi

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy for valuable how-to assets including sample agreements, checklists, flowcharts, and more!

vitsolutionsAuthor Commented:
Hi and thanks for your suggestions, i am very sorry for the late reply, my customer is a little backwards about coming forward with information and there seems to be a time delay. Unable to send email is a big cause of this i suspect.

The customer has advised me no changes have been made to any of the infrastructure or ISP.
if i ping the mail server

ping mail.mvue.uk.net
i get the following results

Reply from bytes=32 time=54ms TTL=56
Reply from bytes=32 time=53ms TTL=56
Reply from bytes=32 time=52ms TTL=56
Reply from bytes=32 time=52ms TTL=56

Ping statistics for
    Packets: Sent = 4, Received = 4, Lost = 0 (0% l
Approximate round trip times in milli-seconds:
    Minimum = 52ms, Maximum = 54ms, Average = 52ms

I can confirm the exchange server routes email using DNS, mx records have been created successfully and as previously mentioned everything was working without fault until recently.
There are no filters applied to mail routing.

I am very intersted in how to set a reverse dns entry? can i have step by step instructions for this? thanks again
No comment has been added to this question in more than 21 days, so it is now classified as abandoned.

I will leave the following recommendation for this question in the Cleanup Zone:

Any objections should be posted here in the next 4 days. After that time, the question will be closed.

f_o_o_k_y Experts Exchange Cleanup Volunteer
PAQed with points refunded (250)

EE Admin

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.