MySQL се бори със заявка във връзка едно към много, съответстваща на множество условия

Това е релационно разделение проблем.

Начинът, който предлагате с COUNT е може би най-лесният в 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

Има друг подход с двойно NOT EXISTS в свързаната статия, но тъй като MySQL не поддържа CTE, това би било доста тромаво.