Exhange 5.5 Relaying Denied

HI there, Im having a problem with one domain being blocked from send us mail. The Undeliverable error is:

The recipient name is not recognised
The MTS-ID of the original message is: c=US;a= ;p=Westfalia Separa; I=MAILSERVER1-020806115718z-1707MSEXCH:IMS: Westfalia Separator Irl Ltd:WESTFALIA:MAILSERVER1 3550 (000B09AA) 550.7.1 <.......> Relaying denied

(Westfalia Sperator being the compnay sending)

The MS Exchange Event ID on the Westfalia side is 4031
The Destination server reported: 550.7.1
Relaying Denied from <....>

(Where <....> is the email address.

Ive checked the routing and all is ok

Any ideas???

Mark