Emails showing up as external from Exchange Online to Exchange 2013 On-Premises

[Michael Gorn]

We are running Exchange 2013 CU21  in Hybrid mode. Emails from Exchange Online users to Exchange On-Premises users is showing up as external.  Transport rules that are supposed to apply only to external emails where "the sender is located" "Outside the organization" are erroneously being applied to emails that Exchange Online users are sending to the On-Premises users.

However, the emails from On-Premises users to Exchange Online users are showing up correctly as internal.

The header "X-MS-Exchange-Organization-AuthAs: Anonymous" is found in emails from Exchange Online to Exchange 2013 On-Premises users. When the emails are sent from Exchange 2013 On-Premises users to Exchange Online users, the header in the emails is "X-MS-Exchange-Organization-AuthAs: Internal". 

How do I fix this, so that the emails are showing as internal both ways?

Thank you.

[#2]

PS C:\Users\> get-remotedomain CompanyName.com|fl

DomainName : CompanyName.com
IsInternal : True
TargetDeliveryDomain : True
ByteEncoderTypeFor7BitCharsets : Undefined
CharacterSet :
NonMimeCharacterSet :
AllowedOOFType : InternalLegacy
AutoReplyEnabled : True
AutoForwardEnabled : True
DeliveryReportEnabled : True
NDREnabled : True
MeetingForwardNotificationEnabled : True
ContentType : MimeHtmlText
DisplaySenderName : True
PreferredInternetCodePageForShiftJis : Undefined
RequiredCharsetCoverage :
TNEFEnabled : True
LineWrapSize : Unlimited
TrustedMailOutboundEnabled : True
TrustedMailInboundEnabled : True
UseSimpleDisplayName : False
NDRDiagnosticInfoEnabled : True
MessageCountThreshold : 2147483647
AdminDisplayName :
ExchangeVersion : 0.1 (8.0.535.0)
Name : CompanyName.com
DistinguishedName : CN=CompanyName.com,CN=Internet Message Formats,CN=Global Settings,CN=Configuration,CN=CompanyName0.onmicrosoft.com,CN=ConfigurationUnits,DC=NAMPR25C003,DC=PROD,DC=OUTLOOK,DC=COM
Identity : CompanyName.com
ObjectCategory : NAMPR25C003.PROD.OUTLOOK.COM/Configuration/Schema/ms-Exch-Domain-Content-Config
ObjectClass : {top, msExchDomainContentConfig}
WhenChanged : 2/21/2019 11:20:58 AM
WhenCreated : 2/19/2019 2:46:14 PM
WhenChangedUTC : 2/21/2019 4:20:58 PM
WhenCreatedUTC : 2/19/2019 7:46:14 PM
OrganizationId : NAMPR25C003.PROD.OUTLOOK.COM/Microsoft Exchange Hosted Organizations/CompanyName0.onmicrosoft.com - NAMPR25C003.PROD.OUTLOOK.COM/ConfigurationUnits/CompanyName0.onmicrosoft.com/Configuration
Id : CompanyName.com
OriginatingServer : CM5PR12A005DC08.NAMPR25C003.PROD.OUTLOOK.COM
IsValid : True
ObjectState : Unchanged

[#3]

Try to use this tool: TagExternal instead of the transport rule.