When a node is not selected to be shown in the node list it is still shown in the advanced search select box. I would guess that this is like an oversight, but in case not, posting this as a tweak.
Ah, it appears that it might be an oversight then. In the advanced search area we are seeing hidden nodes in the "Forum:" field select box under the "Search Everything" tab. The nodes we have seen like this have all been Pages rather than Forum nodes. Perhaps that is where the problem lies. I'll add a bug report with reference to this thread. -- Never mind on that new post looks like this has been moved. Thanks Mike!