Message Undeliverable to External Partie

My users are unable to send external emails, but internal email and receiving from external have no problem.

we have a connector to our France office which will go thru there before sending out the mails. is there anything i can do out at our exchange server 5.5?

we have take measure to restart all services but still no improvement.

help please