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