When doing an OR search, excluding privacy options does not exclude

When I do an OR search with multiple search criteria along with excluding people with the "do not email OR no bulk email" privacy options set. What I expect is to get the contacts matching all of the search criteria and none of those contacts having either "do not email OR no bulk email" checked.

Steps to replicate the issue:
1) Do an advanced OR search with multiple search criteria and select exclude "Do not email OR no bulk email" http://prntscr.com/c4ztw8
2) The contacts returned are way more than it should be.

Steps for the work around:
1) Do the same search as above without selecting anything to exclude
2) Export the contacts
3) Manually sort and remove anyone who has a 1 in the Do not email or the No bulk email column
4) Save the file

As a note i have also applied the fixes in these 2 tickets:
https://issues.civicrm.org/jira/browse/CRM-18585
https://issues.civicrm.org/jira/browse/CRM-19202