Do you use visit dimension or action dimension?
As segments are not filters, the result may not be the one you expect… If during his visit the visitor set the dimension as no_cookie then change as with_cookie, then, for that visit, he will appear in both segments…
Also have a look at: