Could you please tell us:
Where are you trying to send mail to (external or parent server)?
Do the other remote servers work correctly (ie send and receive mail)?
Do you have individual Messaging Configuration documents or a global one for the domain?
Is the mail routing task running on the misbehaving remote server?
REGISTER or login: