Ubuntu sendmail “Relaying denied. Ip name possibly forged” (in reply to rcpt to command)

When I try to send an email (from a different server) to a local account on my server I get the following error:

Relaying denied. IP name possibly forged [W.X.Y.Z]

Here's what I do:

user@a-different-domain.com:~$ telnet subdomain.domain.com 25
Trying A.B.C.D...
Connected to subdomain.domain.com.
Escape character is '^]'.
220 subdomain.domain.com ESMTP Sendmail 8.14.4/8.14.4/Debian-2ubuntu1; ...
HELO a-different-domain.com
250 subdomain.domain.com Hello ...
MAIL FROM: <user@a-different-domain.com>
250 2.1.0 <user@a-different-domain.com>... Sender ok
RCPT TO: <user@subdomain.domain.com>
550 5.7.1 <user@subdomain.domain.com>... Relaying denied. IP name possibly forged [W.X.Y.Z]

The problem is that I can send emails just fine if I use RCPT TO: <user@mail.subdomain.domain.com> instead of RCPT TO: <user@subdomain.domain.com>

Please see below the configuration that I currently use.

DNS Configuration:

Host                 Type  Priority  Redirect to
subdomain.domain.com MX    10        mail.subdomain.domain.com
subdomain.domain.com A     10        A.B.C.D

Email server configuration:

OS: Ubuntu
Email Server: sendmail

In /etc/mail/access I have (among others):

mail.subdomain.domain.com
subdomain.domain.com

/etc/mail/local-host-names:

localhost
mail.subdomain.domain.com
subdomain.domain.com

Regarding the masquerading here is what I have in /etc/mail/sendmail.mc:

MASQUERADE_AS(`subdomain.domain.com')dnl
MASQUERADE_DOMAIN(`subdomain.domain.com.')dnl
MASQUERADE_DOMAIN(localhost)dnl
MASQUERADE_DOMAIN(localhost.localdomain)dnl

Just for clarifications: mail.subdomain.domain.com and subdomain.domain.com point to the same IP address.

================= UPDATE1 =================

@Andrzej A. Filip

Yes, i restarted sendmail.

Here is the output of echo '$=w' | sendmail -Am -bt:

root@subdomain:/etc/mail# echo '$=w' | sendmail -Am -bt
ADDRESS TEST MODE (ruleset 3 NOT automatically invoked)
Enter <ruleset> <address>
> [A.B.C.D]
mail.subdomain.domain.com
[ip6-loopback]
localhost
subdomain
ip6-localhost
[127.0.0.1]
[127.0.0.2]
subdomain.domain.com
[ip6-localhost]
ip6-loopback

================= UPDATE2 =================

I tested and found out (without changing the DNS configuration) that if i add subdomainXXX.domain.com (where subdomainXXX is any string) to /etc/mail/local-host-names and then I test sending an email from a remote server it simply works:

user@remote-server:/# telnet subdomain.domain.com 25
Trying A.B.C.D...
Connected to subdomain.domain.com.
Escape character is '^]'.
220 subdomain.domain.com ESMTP Sendmail 8.14.4/8.14.4/Debian-2ubuntu1; ...
HELO remote-server
250 subdomain.domain.com Hello ....
MAIL FROM: <...>
250 2.1.0 <...>... Sender ok
RCPT TO: <root@subdomainXXX.domain.com>
250 2.1.5 <root@subdomainXXX.domain.com>... Recipient ok

So it works for any subdomain except for the one that I'm interested into (subdomain.domain.com – which is actually the hostname of the server).