Scott, 

I have the same problem as well. The EnsLib_HL7.Messages had records going back years. While I have not found the offending code that creates the orphaned records, I do have a task that purges the records. We happen to have multiple databases and namespaces, so I added this to a general library database called ACLIB. By doing this I can use the same task code to target multiple namespaces. 

I based my code by tracing through some of the InterSystems purge code. 

Include (Ensemble, %sySite)

/// Deletes EnsLib_HL7.Message records without corresponding header resulting in orphaned records
Class ACLIB.Utils.PurgeOrphanedMessages Extends %SYS.Task.Definition
{

/* Task to purge any orphaned messages
Orphaned Message - Message data without corresponding header.Author: Daniel Lee
Date: 2019-07-16
*/
/// How many days of messages should not be purged
Property NumberOfDaysToKeep As %Integer(MINVAL = 0) [ InitialExpression = 30 ];Property MaxCountToPurge As %Integer(MINVAL = 0) [ InitialExpression = 10000 ];/// Which NameSpace to execute the query to delete messages

/* Note that you will want to modify the namespace list or exclude it and modify the code if you only have one namespace*/
Property SourceNamespace As %String(DISPLAYLIST = ",HIE,IMMUNIZATION,PHI,PM,RESULTS", VALUELIST = ",hie,immunization,phi,pm,results") [ Required ];

/// The OnTask() Method is called to execute the task
Method OnTask() As %Status
{

// These time variables are only for logging 
Set tTime = $ZH
Set tDisplayTime = $ZDATETIME($HOROLOG,1,1,9)
Set tDeletedCount = -1

Write tDisplayTime_": Begin purge orphaned messages for "_..SourceNamespace_"."

Set tSC = ..PurgeOrphaned(.tDeletedCount, ..NumberOfDaysToKeep, ..MaxCountToPurge, ..SourceNamespace)
Set tTime = $ZH - tTime
If $$$ISOK(tSC) {
Set msg = "Purged "_tDeletedCount_" records, keeping the last "_..NumberOfDaysToKeep_" days in "_tTime_"s" 
$$$LOGINFO(msg)
Do $$$LOGMSG(msg,0,1)
Write !,msg
}
else
{
Set msg = "Error purging"_..SourceNamespace_" keeping the last "_..NumberOfDaysToKeep_" : "_ $$$StatusDisplayString(tSC)
$$$LOGERROR(msg)
Do $$$LOGMSG(msg,0,3)
Write !,msg
}
Quit tSC
}

ClassMethod PurgeOrphaned(Output pDeletedCount As %Integer, pDaysToKeep As %Integer = 30, pMaxCountToPurge As %Integer = 100000, pNameSpace As %String) As %Status
{
/*
pDeletedCount - number of rows deleted
pDaysToKeep - number of days of records to keep
pMaxCountToPurge - number of records to delete at any one time, added to keep system from timing out*/
New %tID,%tMaxCountToPurge Set %tMaxCountToPurge = pMaxCountToPurge, %tID=""

//This method to get the date was adapted from Ens purge code ... 
New %tDoNotDeleteDate Set %tDoNotDeleteDate = $$$timeUTCHtoUTC($s($ztimezone'<0:($H-pDaysToKeep+1)_","_($ztimezone*60),1:($H-pDaysToKeep)_","_($ztimezone*60+86400)))

Set SQLCODE=0, pDeletedCount=0, tDeletedCount=0, tCursorRowCount=0
Set tNamespace = $NAMESPACE //Used to return to previous namespace
Set $NAMESPACE = pNameSpace//Grab oldest records that exist prior to the time created value as these are orphaned records without headers
 

&sql(DECLARE C1 CURSOR FOR
Select TOP :%tMaxCountToPurge ID, TimeCreated Into :%tID,:%tTimeCreated From EnsLib_HL7.Message 
Where TimeCreated < :%tDoNotDeleteDate 
Order By TimeCreated Asc)&sql(OPEN C1) For { 
&sql(FETCH C1)  
Quit:SQLCODE

&sql(Delete From EnsLib_HL7.Message Where ID=:%tID)

Set tDeletedCount=tDeletedCount+1
Write !,tDeletedCount_"|"_%tID_"|"_%tTimeCreated
} Set tCode=SQLCODE &sql(CLOSE C1) Set:'SQLCODE SQLCODE=tCode
Set pDeletedCount=tDeletedCount
Quit:SQLCODE&&(SQLCODE'=100) $$$ERROR($$$EnsErrGeneral,"Purge error at ID "_%tID _"; SQLCODE = "_SQLCODE)
Set tSC = (SQLCODE=100)&sql(CLOSE C1)
Set $NAMESPACE = tNamespaceQuit tSC
}}

Note that I kept my SQL statement very simple. The full SQL statement to check for orphaned messages is here:

SELECT msg.TimeCreated, COUNT(msg.Id) FROM EnsLib_HL7.Message msg LEFT JOIN Ens.MessageHeader hdr ON msg.Id=hdr.MessageBodyId WHERE hdr.MessageBodyId IS NULL AND msg.Name NOT LIKE '%ACK%' ORDER BY msg.TimeCreated ASC

I tried to format this code by using the ObjectScript button but it looked ugly in the preview. 

Hopefully, this helps.