Query SQL complicata:ricerca di elementi corrispondenti a più chiavi esterne diverse

A condizione che tu abbia indici univoci su entrambi (ProductID, CategoryID) e (ProductID, InvoiceID) :

SELECT  ProductID
FROM    (
        SELECT  ProductID
        FROM    ProductInvoice
        WHERE   InvoiceID IN (1, 2)
        UNION ALL
        SELECT  ProductID
        FROM    ProductCategory pc
        WHERE   CategoryID IN (3, 4)
        ) q
GROUP BY
        ProductID
HAVING  COUNT(*) = 4

oppure, se i tuoi valori sono passati in CSV stringhe:

WITH    catids(value) AS
        (
        SELECT  DISTINCT CAST([value] AS INT)
        FROM    dbo.split(@categories, ' '))
        ), 
        (
        SELECT  DISTINCT CAST([value] AS INT)
        FROM    dbo.split(@invoices, ' '))
        )
SELECT  ProductID
FROM    (
        SELECT  ProductID
        FROM    ProductInvoice
        WHERE   InvoiceID IN
                (
                SELECT  value
                FROM    invoiceids
                )
        UNION ALL
        SELECT  ProductID
        FROM    ProductCategory pc
        WHERE   CategoryID IN
                (
                SELECT  value
                FROM    catids
                )
        ) q
GROUP BY
        ProductID
HAVING  COUNT(*) = 
        (
        SELECT  COUNT(*)
        FROM    catids
        ) + 
        (
        SELECT  COUNT(*)
        FROM    invoiceids
        )

Tieni presente che in SQL Server 2008 puoi passare parametri con valori di tabella nelle stored procedure.