MySQL kämpar med fråga i en till många relationer som matchar flera villkor

Detta är en relationell uppdelning problem.

Sättet du föreslår med COUNT är förmodligen det enklaste i MySQL

SELECT product_id
FROM product_attributes pa
WHERE (attribute='size' and value='medium')
OR (attribute='colour' and value='blue')
GROUP BY product_id
HAVING COUNT(DISTINCT CONCAT(attribute,value) ) = 2

Det finns ett annat tillvägagångssätt med dubbel NOT EXISTS i den länkade artikeln men eftersom MySQL inte stöder CTE:er skulle det vara ganska besvärligt.