NOT Was filters return everyone without that condition.
That is DIFFERENT than saying
Email Address NOT CONTAINS ="X"
Marketo also filters from top to bottom, so that may be an issue here, although they are logically the same. Using OR will provide you with people who meet either or both conditions, so it is possible to get only people with both if that's true in your db.
This is weird. Can you provide screenshots?