Problem with outbound Exchange e-mail

I am running Exchange 5.5 Sp4. I have users who are experiencing problems sending internet e-mail. They receive the following error:

The recipient name is not recognized
The MTS-ID of the original message is: c=US;a= ;p=Crate?Barrel;l=ESCORP1-020502150334Z-27117
MSEXCH:IMS:Crate_Barrel:cbcorp:ESCORP1 3553 (000B09AA) 553 sorry, that domain isn’t in my list of allowed rcpthosts (#5.7.1)

I cannot find anything in the Microsoft knowledge base that matches that error.