This has been confirmed as a bug in the search logic.
The workaround is fairly simple, use the more direct method of searching ( = Yes or = No), or add another criteria of <attribute> exists to your search...
The other issue that can cause a difference is if you don't assign a value to a boolean attribute (leaving the value NULL). In this case, searching for Not = "Yes" is not equal to = "No"... Note: this only occurs if you add a boolean attribute to an Info Item, and Esc without choosing a value...
A fix for these reported problems will be included in a future release of Ultra Recall. Thanks for reporting it.