Sendmail fails to external addresses

[bob doe]

I had put up a topic earlier but deleted it as I progressed on this issue.

My end goal is I have a webserver which I want to be able to send out email (does not require to send in). I do have an STMP relay server specified and I can send emails to internal addresses just fine, but when I send to an external address I get the following:

-----
# mailx email@gmail.com
Subject: test
test
Cc:
Can't send mail: sendmail process failed with error code 67
-----

The log for the appropriate sending is:

-----
Dec 18 16:38:27 host sendmail[3810]: qBILcR2v003810: from=root, size=45, class=0, nrcpts=1, msgid=<201212182138.qBILcR2v003810@host.mydomain.com>, relay=root@localhost
Dec 18 16:38:32 host sendmail[3810]: qBILcR2v003810: to=email@gmail.com, ctladdr=root (0/0), delay=00:00:05, xdelay=00:00:05, mailer=relay, pri=30045, relay=relay.mydomain.local. [192.168.3.1], dsn=5.7.1, stat=User unknown
Dec 18 16:38:42 host sendmail[3810]: qBILcR2v003810: qBILcR2w003810: DSN: User unknown
Dec 18 16:38:42 host sm-mta[3866]: qBILcg7j003866: from=<>, size=2082, class=0, nrcpts=1, msgid=<201212182138.qBILcR2w003810@host.mydomain.com>, proto=ESMTP, daemon=MTA, relay=host.mydomain.com [127.0.0.1]
Dec 18 16:38:42 host sendmail[3810]: qBILcR2w003810: to=root, delay=00:00:00, xdelay=00:00:00, mailer=relay, pri=31069, relay=[127.0.0.1] [127.0.0.1], dsn=2.0.0, stat=Sent (qBILcg7j003866 Message accepted for delivery)
Dec 18 16:38:42 host sm-mta[3867]: qBILcg7j003866: to=<root@host.mydomain.com>, delay=00:00:00, xdelay=00:00:00, mailer=local, pri=32336, dsn=2.0.0, stat=Sent
-----

I know the issue is not with the relay server, as it is an Exchange server and can send to anyone just fine.

I've tried multiple external domains... gmail, hotmail... none work. However I can send emails to any address inside the @mydomain.com just fine.

I realize sendmail may be old and/or replaced with postfix, and at first I tried postfix earlier this morning, but I couldnt get it sending emails at all..

Thanks for any help.