Index Scan Vs Index Seek

I have a really strange problem.

I execute this query:

declare @cid int
set @cid = 2003227

select * from sales s, product p where p.product_Id = s.product_Id and customer_id = @cid

select * from sales s, product p where p.product_Id = s.product_Id and customer_id = @cid or @cid = 0

3 Million rows in sales, 120000 in product.

The first does and index seek, the second an index scan.
The execution plan reports that the scan takes 99.87% of the cost, and the seek takes 0.13%

This problem obviously gets worse the bigger the dataset / query /etc.

The reason I query this, is because it never used to take this long to do index scans. Is there something i can change, something i can fix?

Any help would be appreciated.

Josh