Thank you for the replies.

- As for now, I would like to find a solution without changing the query if possible.
- I changed the query in my post to reflect the query in the trace (@P1, @P2, @P3, @P4, @P5)
- Partition is not selective at all, in fact all the rows have the same partition.
- DATAAREAID can be two values, let's say 50/50 distribution.
- Unfortunately, I can not get rid of PARTITION and DATAAREAID since the system is designed that way. PARTITION will always be the first column and DATAAREAID will always be the second column in the index.

DATATYPE, DATASOURCE, FILEREFRECID and AXMATCHINGCODE are the real filters.

In the slow execution plan:
Seek Predicate: PARTITION, DATAAREAID
Predicate: DATATYPE, AXMATCHINGCODE

In the fast execution plan:
Seek Predicate : PARTITION, DATAAREAID, FILEREFRECID
Predicate: FILEREFRECID

Maybe I don't understand the Non-Cluster Seek Operation, but it is clear that PARTITION + DATAREAID + FILEREFRECID will return less rows than PARTITION + DATAAREAID. Is it a clue ? 
Does SQL perfom a first read on the Seek Predicate and then another read for the Predicate on a smaller set of data ?
Where exactly does SQL filter DATASOURCE?

I am not expecting a full explanation from community, but your questions and remarks help me to understand better!

Thank you