Consulta avançada (?) E/OU

Eu tenho que dizer - estou perplexo. Não consigo pensar em nenhuma solução que chegue nem perto. Eu tentaria procurar uma solução nestas direções:

Funções agregadas definidas pelo usuário. Talvez você possa fazer uma função que tome como argumento a expressão desejada (em uma sintaxe simplificada) e as linhas para uma única pessoa. A função então analisa a expressão e a compara com as linhas. Hmm... talvez o MySQL inclua alguma função agregada de concatenação e uma função de correspondência de regex? Esta pode ser uma solução então (embora provavelmente não seja muito rápida).
Funções analíticas. Não pretendo entendê-los, mas, por mais que eu saiba sobre eles, acho que geralmente estão nessa direção. Embora eu não saiba se haverá uma função que atenda a essa necessidade.

Adicionado: Ah, acho que entendi! Embora eu acho que o desempenho será miserável. Mas isso vai funcionar! Por exemplo, se você precisar pesquisar 1 AND 2 AND (3 OR 4) então você escreveria:

SELECT
    *
FROM
    Persons A
WHERE
    EXISTS (Select * from PersonCriteria B WHERE A.PersonID=B.PersonID AND CriteriaID=1)
    AND
    EXISTS (Select * from PersonCriteria B WHERE A.PersonID=B.PersonID AND CriteriaID=2)
    AND
    (
        EXISTS (Select * from PersonCriteria B WHERE A.PersonID=B.PersonID AND CriteriaID=3)
        OR
        EXISTS (Select * from PersonCriteria B WHERE A.PersonID=B.PersonID AND CriteriaID=4)
    )

2 adicionados: Aqui está outro, embora o desempenho provavelmente seja ainda pior:

SELECT p.* FROM Person p
    JOIN (select PersonID from PersonCriteria WHERE CriteriaID=1) c1 ON p.PersonID=c1.PersonID
    JOIN (select PersonID from PersonCriteria WHERE CriteriaID=2) c2 ON p.PersonID=c2.PersonID
    JOIN (select PersonID from PersonCriteria WHERE CriteriaID IN (3,4)) c3 ON p.PersonID=c3.PersonID

3 adicionados: Esta é uma variação do nº 2, mas isso pode realmente ter uma chance de um desempenho decente!

SELECT p.* FROM
    Person p
    JOIN PersonCriteria c1 on (p.PersonID=c1.PersonID AND c1.CriteriaID=1)
    JOIN PersonCriteria c2 on (p.PersonID=c2.PersonID AND c2.CriteriaID=2)
    JOIN PersonCriteria c3 on (p.PersonID=c3.PersonID AND c3.CriteriaID IN (3,4))

Se você adicionar um índice a PersonCriteria em colunas (PersonID,CriteriaID) (exatamente nesta ordem!), então acho que é o mais rápido que você obterá em qualquer caso.