I think you're doing it right, but you might check if EXCEPT gives you better performance:
select C.CustID, P.ProdID
from @customers C
cross join @products P
EXCEPT
SELECT CustID, ProdID
from @sales S
group by CustID, ProdID
And obviously if you can pare down the client list, it would help, like eliminating anyone who hasn't purchased anything in the last year.