¿Qué consulta mysql debo usar para seleccionar una categoría que coincida con TODOS mis criterios?

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
        )

Necesitas tener un UNIQUE índice en (cat_id, product_id) (en este orden) para que funcione rápido.

Esta solución utilizará INDEX FOR GROUP BY para obtener una lista de categorías distintas y EXISTS el predicado será un poco más rápido que COUNT(*) (ya que la agregación requiere algunos gastos generales).

Si tiene más de dos productos para buscar, ajuste el primer argumento a LIMIT en consecuencia.

Debería ser LIMIT n - 1, 1 , donde n es el número de artículos en el IN lista.

Actualización:

Para devolver las categorías que contienen todos los productos de la lista y nada más, use esto:

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)
        )