One of the key things with segments is understanding the different between "does not exist" and "excludes".
If you set up a condition in a visit segment with "does not exist", it's going to look in that entire visit for a value that is something other than the one you want to exclude. For example, if I don't want to see the homepage and I do "visit with page does not contain homepage". It's going to return all visits where someone saw a page that was not the homepage, regardless of if one of the other pages was home or not. The only thing that won't be returned is visits where the only page seen was homepage.
Alternatively, there's the "excludes" option. If you do "visit where page = homepage" and then use the "exclude" option, it's going to look for any visit that saw the homepage and then NOT return those visits, it will only return other visits.
So, what you're seeing isn't a bug, it is working as intended. To get what you need, try using "exclude" instead.