SMTP Error after Changing Gateway

We have two gateways(two different links) for the internal network to access the Internet. And we have a Linux mail server with a public IP. We are having problem to send email when changing PC's default gateway from A to B, the error message getting from Outlook Express is "The message could not be sent because one of the recipents was rejected by the server. The rejected e-mail address was 'xxx@xxx', Subject 'xxx', Account: 'xxx', Server: 'xxx', Protocol: SMTP, Server Response: '551 5.7.1 we do not relay', Port: 25, Secure(SSL): No, Server Error: 551, Error Number: 0x800CCC79"

Change the default gateway back to A then it works fine. Our PCs have Windows 2000, 98 and NT, with Outlook or Outlook Express.

How can we fixed the problem?