MySQL luchando con la consulta en una relación de uno a muchos que coincide con múltiples condiciones

Este es un división relacional problema.

La forma en que sugieres con el COUNT es probablemente el más fácil en 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

Hay otro enfoque con doble NOT EXISTS en el artículo vinculado, pero como MySQL no es compatible con CTE, eso sería bastante engorroso.