Am I just completely missing something, here?
Yes. I was.
In case anyone else runs into this...
Turns out that these old rules were using 'not equal' logic to compare against fields that are typically not used anymore - i.e. they're left blank unless there's some reason to populate them, whereas in the past they had been randomly used... or not. Seems to have depended on who added the node, what other 23423 things they were doing at the same time, etc.
When using a not equal comparison, rows that have that field null are not returned in the result.
So, taking my 86-object example above, the comparison was Department <> DeptA. The 86 resulting nodes were all ones that had been added way back when, marked as DeptB, DeptC, etc. All of the nodes added later on which had no Department value were not part of the set returned.