Advanced Search AND Operator doesn't operate for Multiple Tags Search (at least)
I think the AND operator applies between fields, not within options of a field.
If you want to search TagX AND TagY you can do this in Search Builder.