I'm trying to make this work with a variety of different sendmail versions (all 8.8 or better) and different OS's.

I have to configure all my unix workstations to deliver all email through a relay 'smtp.mydomain.com'. This includes unqualified names as well as qualified names and remote addresses.

The host 'smtp.mydomain.com' does not accept mail addressed to @smtp.mydomain.com and it isn't in my control to change that.

I've played around with MAIL_HUB, SMART_HOST, LOCAL_RELAY, always_add_domain, allmasquerade, masquerade_entire_domain, masquerade_envelop and pretty much every feature or setting related to address rewriting.

FROM addresses are correctly re-written with @mycomain.com, however I need unqualified recipient addresses to be rewritten with @mydomain.com and NOT @smtp.mydomain.com, which is what seems to be happening.

I tried passing the optional argument of 'mydomain.com' to the always_add_domain feature however sendmail is still tryign to deliver the maili to "user@smtp.mydomain.com" which gets rejected.

Although I need this to work on AIX, Solaris (8,9 & 10) and RHEL (3,4,5) I'm currently working with RHEL5.2 and Sendmail 8.13.8. I'm using m4 for configuration and created a stripped down sendmail.mc file:
(This is the hacked to pieces version which probably contains plenty of errors at this point)

------------------
divert(-1)dnl
include(`/usr/share/sendmail-cf/m4/cf.m4')dnl
VERSIONID(`RHEL5 2009/10/19')dnl
OSTYPE(`linux')dnl
define(`SMART_HOST', `smtp.mydomain.com')dnl
define(`MAIL_HUB', `smtp.mydomain.com')dnl
define(`LOCAL_RELAY', `smtp.mydomain.com')dnl
MASQUERADE_AS(`mydomain.com.')dnl
FEATURE(masquerade_envelope)dnl
FEATURE(masquerade_entire_domain)dnl
FEATURE(allmasquerade)dnl
MASQUERADE_DOMAIN(localhost)dnl
MASQUERADE_DOMAIN(localhost.localdomain)dnl
FEATURE(redirect)dnl
FEATURE(always_add_domain, `mydomain.com')dnl
EXPOSED_USER(`root')dnl
DAEMON_OPTIONS(`Port=smtp,Addr=127.0.0.1, Name=MTA')dnl
FEATURE(`accept_unresolvable_domains')dnl
LOCAL_DOMAIN(`localhost.localdomain')dnl
MAILER(smtp)dnl

had a similar problem just now, hope this helps

FEATURE(`stickyhost')
Sendmail cf/README - Features

used with mail_hub, the message keeps its enveloped address, ie. not changed to @mail_hub