Note in general users are searching for objects not metadata. Taxonomies are metadata about objecs such as post types. Search terms may be terms found in natural properties or metadata properties of objects. So basically you should treat taxonomy values as index terms on objects just like title, description or content, etc.
I would have thought the search process when using the index table is to find an object which is indexed by term1 AND term2 regardless of how the terms and index where sourced. In any scenario where metadata terms are used as source terms for object indexing ( e.g. tags) it is never going to be the case that one metadata terms has two values. The only possible way to use AND is to assume that term1 and term2 may both refer to the same object and the objective is to find which object(s) for which there is a term1 AND a term2 in the index table that refer to the same object.
If there was no metadata used, and you indexed the text of objects containing strings of text values (e.g. term3, term4), then a search for term3 AND term4 would return any objects where term3 AND term4 both refer to the same object. When metadata terms are used, it is a straight-forward concept to use AND in the same way. Effectively the metadata terms (e.g. tags or any other taxonomy) should act as if the metadata terms were actually contained by the object.
Suppose object1 contains text: “The happy fox”, and has metadata terms (e.g. tags): “brown”, “quick”. Indexing object1 text produces index terms “happy”,”fox”, and indexing the metadata produces additional index terms “brown”, “quick” for the same object. Thus a search for “happy” AND “fox” should produce the same result (object1) as a search for “quick” AND “brown” or “brown” and “happy”. All these should be terms in the same index table with references to the same object types.
In WordPress, the primary object types are post types (standard and custom post types). Additional object types could be comments and users. All of your sources would be simply data elements referencing obect types. So my expectation is that all terms including tags, categories, titles, descriptions, text content, dates, name, status, custom taxonomies, etc should be treated equally. Potentially your sources for post types could be derived from any column of the post, postmeta, terms, etc.