Better way to select products that are related to ALL of the categories?
This might work for you, should perform better.

WITH CTE_ProductCount AS
(
    SELECT PC.ProductID
        , COUNT(PC.CategoryID) AS ProductCount
    FROM ProductCategoryRelation PC
    WHERE PC.CategoryID IN (1,2,3)
    GROUP BY PC.ProductID
    HAVING COUNT(PC.CategoryID) = 3
)
SELECT *
FROM Product
    INNER JOIN CTE_ProductCount PC ON PC.ProductID = Product.ProductID;