Nu,ber OF ROWS
235 000 category_product
58 000 products

Relational division:

SELECT SQL_NO_CACHE p.*
FROM product_entries p
INNER JOIN
(
    SELECT product_version_id
    FROM category_product_version
    WHERE category_id IN (35, 41)
    GROUP BY product_version_id
    HAVING COUNT(DISTINCT category_id) = 2
) pc
    ON p.product_version_id = pc.product_version_id

2826 ROWS  ~ 20ms

SELECT SQL_NO_CACHE p.*
FROM product_entries p
INNER JOIN
(
    SELECT product_version_id
    FROM category_product_version
    WHERE category_id IN (35,41,706,726,727)
    GROUP BY product_version_id
    HAVING COUNT(DISTINCT category_id) = 5
) pc
    ON p.product_version_id = pc.product_version_id

46 ROWS ~ 25-30 ms

====
Multiple sub-queries:

SELECT SQL_NO_CACHE p.*
FROM product_entries p
WHERE EXISTS
(
    SELECT 1
    FROM category_product_version
    WHERE product_version_id = p.id
    AND category_id = 35
)
AND EXISTS
(
    SELECT 1
    FROM category_product_version
    WHERE product_version_id = p.id
    AND category_id = 41
)

2826 ROWS ~ 5-7ms

SELECT SQL_NO_CACHE p.*
FROM product_entries p
WHERE EXISTS
(
    SELECT 1
    FROM category_product_version
    WHERE product_version_id = p.id
    AND category_id = 35
)
AND EXISTS
(
    SELECT 1
    FROM category_product_version
    WHERE product_version_id = p.id
    AND category_id = 41
)
AND EXISTS
(
    SELECT 1
    FROM category_product_version
    WHERE product_version_id = p.id
    AND category_id = 706
)
AND EXISTS
(
    SELECT 1
    FROM category_product_version
    WHERE product_version_id = p.id
    AND category_id = 726
)
AND EXISTS
(
    SELECT 1
    FROM category_product_version
    WHERE product_version_id = p.id
    AND category_id = 727
)

46 ROWS ~ 30 ms

One other example:

SELECT SQL_NO_CACHE *
FROM product_entries p
WHERE
    (
        SELECT
            COUNT(DISTINCT cp.category_id)
        FROM category_product_version AS cp
        WHERE
            cp.product_version_id = p.product_version_id AND
            cp.category_id IN (35, 41)
    ) = 2

.... quit the process BEFORE it could RETURN a RESULT