MySql is not optimizing the query properly
The MySQL optimizer cannot optimize expressions in this format:

WHERE (col_1,col_2) IN ((a,b),(c,d),(e,f))


It's not a matter of getting the indexes right -- it appears that it's just not implemented.

The optimizer does not understand that this is equivalent to...

WHERE (col_1,col_2) IN ((a,b)) 
   OR (col_1,col_2) IN ((c,d)) 
   OR (col_1,col_2) IN ((e,f)) 


... or ...

WHERE (col_1 = a AND col_2 = b)
   OR (col_1 = c AND col_2 = d)
   OR (col_1 = e AND col_2 = f)


There's Bug #35819, which I originally found in this article, which was in turn mentioned in the comments on this post.

Unfortunately, I didn't find those until I had already broken out the new Optimizer Trace in MySQL 5.6 and run a few test cases through it.  It seemed like a safe bet that if 5.6 couldn't handle it, then previous versions couldn't handle it.

It turns out that MySQL 5.6 indeed cannot handle it.  The "set in set of sets" construct seems to simply not be something the optimizer catches on to.  So in this case, it's not a matter of the optimizer choosing a full table scan over other plans -- the optimizer actually concludes that there aren't even any other possible plans to consider.  

This is only true for multiple "row constructors" on the right hand side of IN.  For a single expression, the optimizer does its thing and realizes this is equivalent to col_1 = a AND col_2 = b:

WHERE (col_1,col_2) IN ((a,b))    # is optimized correctly
WHERE (col_1,col_2) IN (ROW(a,b)) # is an equivalent expression in MySQL


Interestingly, your original EXPLAIN suggests the unique index was not being used in exactly the way that you may have believed it was being used, at any rate.  It was only being used to find rows with the desired sale_id... not both values.

You'll notice in your original EXPLAIN that the key_len is shown as 4, meaning only the leftmost 4 bytes of the index are going to be examined -- sale_id, a 4-byte INT would be the leftmost 4 bytes in that index.  The Using where means the optimizer realizes that additional filtering of the rows returned from the range scan may be needed to eliminate any rows that don't satisfy the rest of the WHERE clause -- all rows with sale_id 502 and 504 are being retrieved via the index regardless of their value for product_id, and then the resulting rows will be subsequently filtered to satisfy the additional constraints imposed by the WHERE.

The optimum path is probably to stick with (expr and expr) or (expr and expr) or (expr and expr) in your where clause.  It's logically equivalent and the optimizer understands it.

Additional note, regarding some of your comments... in light of what I've discussed above, index hints will not help, because the optimizer appears unaware of the equivalence of the expression you've used to other expressions that it could handle... but as a point of reference, the reason it was syntactically invalid is that you have to use the name of the index, not the list of columns in the index.  You've called your unique index 'UNIQUE', so the way to use this as an index hint would be in this format:

USE INDEX(`UNIQUE`)