>>if "NOT" it is the culprit
>>

>> WHERE Client.NoProvince=@NoProvince AND
>>  (Client.Status>=@Status   OR Client.NoStatus<>@NoStatus)  AND
>>  (Client.Status>=@Status2  OR Client.NoStatus<>@NoStatus2) AND
>>  (Client.Status>=@Status3  OR Client.NoStatus<>@NoStatus3) AND
>>  (Client.Status>=@Status4  OR Client.NoStatus<>@NoStatus4) AND
>> Client.NoCountry IN (1,2,3,4,5,6,7) AND
>> Client.FirstName LIKE @LXList1Clm_No
>>

>
>I verified the execution plan with the NOT approach and with yours. The execution plan is the same in both.
>
>So, I do not think I will be able to simplify thing ups using that approach.

My suggestion was purely aesthetic,
being the logical equivalent, it is very
unlikely that the plan executive changes.
You can try to using the optimization wizard,
and see if some statistics and some index provides
a most efficient plan.