que consulta mysql devo usar para selecionar uma categoria que corresponda a TODOS os meus critérios?

SELECT  cat_id
FROM    (
        SELECT  DISTINCT cat_id
        FROM    cat_product
        ) cpo
WHERE   EXISTS
        (
        SELECT  NULL
        FROM    cat_product cpi
        WHERE   cpi.cat_id = cpo.cat_id
                AND product_id IN (2, 3)
        LIMIT 1, 1
        )

Você precisa ter um UNIQUE indexar em (cat_id, product_id) (nesta ordem) para que isso funcione rapidamente.

Esta solução usará INDEX FOR GROUP BY para obter uma lista de categorias distintas e EXISTS predicado será um pouco mais rápido que COUNT(*) (já que a agregação requer alguma sobrecarga).

Se você tiver mais de dois produtos para pesquisar, ajuste o primeiro argumento para LIMIT adequadamente.

Deve ser LIMIT n - 1, 1 , onde n é o número de itens no IN Lista.

Atualização:

Para retornar as categorias que contêm todos os produtos da lista e nada mais, use isto:

SELECT  cat_id
FROM    (
        SELECT  DISTINCT cat_id
        FROM    cat_product
        ) cpo
WHERE   EXISTS
        (
        SELECT  NULL
        FROM    cat_product cpi
        WHERE   cpi.cat_id = cpo.cat_id
                AND product_id IN (2, 3)
        LIMIT 1, 1
        )
        AND NOT EXISTS
        (
        SELECT  NULL
        FROM    cat_product cpi
        WHERE   cpi.cat_id = cpo.cat_id
                AND product_id NOT IN (2, 3)
        )