Why does querying for records that violate a foreign key return incorrect results?
This is a fairly active database 


If you can restore a static backup somewhere, and do analysis on that unchanging copy, I think you'll find that the weird behavior you're seeing goes away. 

Read Committed

The default isolation level in SQL Server is READ COMMITTED. Under this isolation level, you read the data that is currently committed to the database. The only guarantee that it provides is that when SQL Server reads a given page, it will never return an uncommitted result (known as a dirty read).

In your case you're scanning two tables and comparing them. While SQL Server is doing that scan, there is data movement. 


You read the first few pages of data and have the first bit of data. 
Some of the rows you haven't read yet are updated. Perhaps the MessageSubject or some other column is updated to a longer value, and this results in a page split. Or perhaps the key column is updated and the row is physically moved "up" the index into the portion you already read. 
In both cases, it's possible for a row (or many rows) to move from a place you haven't yet read to a place you already read. You'll never see the row because it moved around. This causes the row to be "missing" from your scan. 
It's also possible a row moves in the other direction: from a place you've already read to a spot you haven't gotten to yet. In this case, you'll see that row twice and your results will have a mysterious double result. 


Your examples use integers, but in your question you mention uniqueidentifier. Since uniqueidentifiers are random, the randomness means rows are constantly being inserting into random places on the table. This increases the chances that a page fills up and has to be split to accommodate the new page, and increases the chances you see these phenomena.

Read the section titled "Locking Read Committed Behaviours" in the above linked article for a thorough explanation.

The fix?

If you want to avoid these off phenomena, don't use the default isolation level in SQL Server. My favorite &amp; default isolation level is READ COMMITTED SNAPSHOT, which avoids these problems. (Read about all the isolation levels here to decide which one is right for you.) 

Or if it's just for a one-time analysis, you could use a database snapshot to create a static image to query, or you could stop writing to the database, or restore a copy elsewhere. Stopping writes will stop data movement, and you won't run into the problem.