No way to tell without seeing the indexes and exec plan. Probably the indexes don't support the additional predicates, possibly combined with row estimation errors (NOT is a little hard to estimate) produces a plan that's highly sub-optimal.

The NOT outside the bracket can be converted to the negative of the two conditions inside, with an OR rather than an AND, and ORs require quite different indexing than ANDs do.

WHERE sales.date = 20130131

AND customers.cus_no NOT IN ('1','2','3')

AND NOT ( customers.cus_no IN ( '4','5')

AND sales.prod_type <> 'Bike'

)

means (via De Morgan's laws)

WHERE sales.date = 20130131

AND customers.cus_no NOT IN ('1','2','3')

AND (customers.cus_no NOT IN ( '4','5') OR sales.prod_type = 'Bike')

which can further be expanded to

WHERE (sales.date = 20130131 AND customers.cus_no NOT IN ('1','2','3','4','5'))

OR (sales.date = 20130131 AND customers.cus_no NOT IN ('1','2','3') AND sales.prod_type = 'Bike')

That OR is probably what's messing the query up.