>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.