Wondering why I'm getting error 550's

I have a user thats trying to send email to some people at a particular domain, and we're only getting a bounceback error message:

Your message did not reach some or all of the intended recipients.

      Subject:      test again
      Sent:      2/14/2006 10:19 AM

The following recipient(s) could not be reached:

      person1@alohaairlines.com on 2/14/2006 10:20 AM
            There was a SMTP communication problem with the recipient's email server.  Please contact your system administrator.
            <mvnp-mail.mvnp.com #5.5.0 smtp;550 person1@alohaairlines.com... Relaying denied>

      person2@alohaairlines.com on 2/14/2006 10:20 AM
            There was a SMTP communication problem with the recipient's email server.  Please contact your system administrator.
            <mvnp-mail.mvnp.com #5.5.0 smtp;550 person2@alohaairlines.com... Relaying denied>

The wierd thing is that this is only intermittent.  My users will be able to send one day, but not another.  The domain we're trying to send to has six MX records:

alohaairlines.com.s8a1.psmtp.com. 100 64.18.7.10 [US]
alohaairlines.com.s8a2.psmtp.com. 200 64.18.7.10 [US]
alohaairlines.com.s8b1.psmtp.com. 300 64.18.7.10 [US]
alohaairlines.com.s8b2.psmtp.com. 400 64.18.7.10 [US]
aqmail.alohaairlines.com. 500 63.167.91.250 [US]
info.alohaairlines.com. 515 66.250.53.112 [US]

I used the email tester from www.dnsstuff.com (EDIT:  sorry wrong webpage) and the first four showed ok.  The aqmail was unresponsive, and the info is my closest link to the problem showing that it could not relay.  At this point, I'm not sure what to do.  My users report that this usually lasts a day or so, then it clears up, but this is definitely not a solution.  Can anyone shed some light on this?
kwan_lauAsked:
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.

SembeeCommented:
This almost certainly is a problem with the remote end. They have put invalid servers in to their MX records. They have actually gone against the recommendations of Postini and have servers that are outside of Postini in their MX configuration.

If you are regularly sending email to this site then you could configure your own server to send to the first four only. This would mean using an SMTP Connector for that domain only, with each of the servers listed as the smart hosts.

http://www.amset.info/exchange/smtp-connector.asp

Basically what is happening is Exchange is trying to use the lower weighted MX records. There is no way you can control 100% which server Exchange will use, unless you use an SMTP Connector.

Simon.

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
kwan_lauAuthor Commented:
Thank you Sembee.  Been tearing out my hair on this one for a month!  The admin on the other side didn't know what was wrong either, and I'll make sure to forward this to them also.
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
Exchange

From novice to tech pro — start learning today.