we have RH 9 with sendmail, apache and php, In php we use it to send email, like welcome email and etc.

Our emails are autmatically relayed to our mail server, from our Main Network(we are just a department), i'll name the mail server as
mailserver.domain.com, but looking at my sendmail.mc ( mailserver.domain.com doesn't exist) and my experience before a fresh installation can automatically use the mailsever.domain.com as a relay server(maybe im just too noob)

problem now, is that the mailserver.domain.com is block when I telnet to it at port 25 It cannot pass through, the admin says that we should use the other mail server that is we are connected now, so their is the new mail server I named it newmailserver.domain.com, I was able to telnet it and send password.

Now my problem is how to make that new mail server be used by sendmail, I did try to modify sendmail.mc and uncomment the smart host, and added the new mail server.

Now Im having another weird things on my maillog

Any clue what should I do next? (ahem my story is a little long one)