How to get rid of messages addressed to not existing subdomains

I have small problem with my sendmail server and need your little help 🙂

My situation is as follow:

User mailboxes are placed on MS exchanege server and all mail to and from outside world are relayed trough my sendmail box.

Exchange server ----- sendmail server ------ Internet

My servers accept messages for one main domain (say, my.domain.com) and for few other domains (let we narrow it too just one, say my_other.domain.com). After configuring sendmail with showed bellow abbreviated sendmail.mc file, essentially everything works ok, but there is small problem. I want to reject messages addressed to not existing recipients as soon as possible (to avoid sending non delivery reports), so my sendmail server make LDAP queries to exchange server, validating every recipient address. This works well both domains but not for subdomains. Such subdomains do not exist, but someone (I'm mean those heated spamers 🙂 could try addresses like this:

user@any_host.my.domain.com 

or

user@any_host.my_other.domain.com

and for those addresses results are as follows:

1. Messages to user@sendmail_hostname.my.domain.com are rejected with error "Unknown user" (due to additional LDAPROUTE_DOMAIN line in my sendmail.mc file, and this is expected behaviour)
2. Messages to user@any_other_hostname.my.domain.com are rejected with error "Relaying denied". Little strange to me, why this time the error is different, but still ok. After all message was rejected and I don't care very much what error code will be returned to sender (spamer).
3. Messages to user@sendmail_hostname.my_other.domain.com and user@any_other_hostname.my_other.domain.com are rejected with error "Unknown user" but only when, there is no user@my_other.domain.com mailbox (on exchange server). If such mailbox exist, then all three addresses (i.e. user@my_other.domain.com, user@sendmail_hostname.my_other.domain.com and user@any_other_hostname.my_other.domain.com) will be accepted. (adding additional line LDAPROUTE_DOMAIN(my_sendmail_host.my_other.domain.com) to my sendmail.mc file don't change anything)

My abbreviated sendmail.mc file is as follows (sendmail 8.14.3-5). Both domains are listed in /etc/mail/local-host-names file (FEATURE(use_cw_file) ):

define(`_USE_ETC_MAIL_')dnl
include(`/usr/share/sendmail/cf/m4/cf.m4')dnl
OSTYPE(`debian')dnl
DOMAIN(`debian-mta')dnl
undefine(`confHOST_STATUS_DIRECTORY')dnl        
define(`confRUN_AS_USER',`smmta:smmsp')dnl

FEATURE(`no_default_msa')dnl
define(`confPRIVACY_FLAGS',`needmailhelo,needexpnhelo,needvrfyhelo,restrictqrun,restrictexpand,nobodyreturn,authwarnings')dnl
FEATURE(`use_cw_file')dnl
FEATURE(`access_db', , `skip')dnl
FEATURE(`always_add_domain')dnl
MASQUERADE_AS(`my.domain.com')dnl
FEATURE(`allmasquerade')dnl
FEATURE(`masquerade_envelope')dnl

dnl define(`confLDAP_DEFAULT_SPEC',`-p 389 -h my_exchange_server.my.domain.com -b dc=my,dc=domain,dc=com')dnl 
dnl define(`ALIAS_FILE',`/etc/aliases,ldap:-k (&(|(objectclass=user)(objectclass=group))(proxyAddresses=smtp:%0)) -v mail')dnl

FEATURE(`ldap_routing',, `ldap -1 -T<TMPF> -v mail -k proxyAddresses=SMTP:%0', `bounce')dnl
LDAPROUTE_DOMAIN(`my.domain.com')dnl
LDAPROUTE_DOMAIN(`my_other.domain.com ')dnl
LDAPROUTE_DOMAIN(`my_sendmail_host.my.domain.com')dnl
define(`confLDAP_DEFAULT_SPEC', `-p 389 -h "my_exchange_server.my.domain.com" -d "CN=sendmail,CN=Users,DC=my,DC=domain,DC=com" -M simple -P /etc/mail/ldap-secret -b "DC=my,DC=domain,DC=com"')dnl

FEATURE(`nouucp',`reject')dnl
undefine(`UUCP_RELAY')dnl
undefine(`BITNET_RELAY')dnl
define(`confTRY_NULL_MX_LIST',true)dnl
define(`confDONT_PROBE_INTERFACES',true)dnl
define(`MAIL_HUB',` my_exchange_server.my.domain.com.')dnl
FEATURE(`stickyhost')dnl

MAILER_DEFINITIONS
MAILER(smtp)dnl

Could someone more experienced with sendmail advice my how to reject messages to those unwanted subdomains?

P.S. Mailboxes @my_other.domain.com are used only for receiving messages and never for sending.