As the subject states,
MAILER-DAEMON@messagelabs.com:
<....@ford.com>:
Connected to 136.1.7.8 but sender was rejected.
Remote host said: 501 Sender domain must exist
As it obviously checks only the first MX record if there are A records,
and if there are none it rejects it. This while there are AAAA records
on the first MX, and even A records on the remaining MXs. Thus a proper
fix would already be to check the other MXs and of course to check for
AAAA too 
And that affects all customers at messagelabs, thus if somebody can pass
that along to them to fix it, that would be great
Oh and of course the check is also there for postmaster@ thus no way to
tell them through that route.
Greets,
Jeroen
I'll get someone to contact Ford and see what they are running. From google it looks like Exchange. Is this a known bug with Exchange? If so I think there's bigger problems than messagelabs 
Jeroen Massar wrote:
Ah good catch, indeed the messagelabs.com SMTP is not the blame here, it
forwards it internally to a ford.com one which rejects it.
One of the mail servers that is broken in that respect upto a very
recent version is Communigate Pro.
As for the backscatter that the above setup can generate, you might want
to implement the same checks on the front-ends, or at least ask the
customers you are forwarding to to disable these checks at least for
your frontend servers as now as you can see, the messagelabs.com smtp
accepted the email and then started rejecting it. If somebody thus
nicely 'forges' (well just fills in a random) email address, the
ford.com server will reject it, and messagelabs starts spamming them
with the full message which is included in the bounce....
Oh, gee, now lets hope spammers don't abuse that 'feature' eh...
Greets,
Jeroen