I started in InterSystems in April 2012 and spent nearly 8 years in Support before moving in Sales Engineering. I consider myself a generalist professionally and personally. I dabble in everything and have a passion understanding how things work together.
Jeffrey,
The scenario that I can hypothesize that would produce these results are around the client timing out before the query finishes executing on the server.
Query 1 fails because you have to do a join on the two large tables and your only where clause is against a property that is not indexed.
Query 2 succeeds because object IDs are "indices by nature".
Query 3(from your comment) succeeds because you are filtering out hundreds, thousands, maybe millions of Ens.MessageHeader objects in your join by using a where clause against and indexed MessageBodyClassName property.
I would recommend reaching out to InterSystems WRC to review the query cost and overall performance to confirm or dive deeper into the failures.
Hypothesis debunked. 
I'm sure there are logs somewhere in Windows or even the driver that can help identify what is at the root of the failure cases. Our WRC can definitely help you with that.
Matthew,
This is difficult to debug from the screenshots provided. I would suggest reaching out to InterSystems directly. Either your Sales Engineer or the WRC would be able to help you work through this road block building out your Batch Record Map.