Okay, you were close 
Change Clients.Not(Contains(...)) to Not(Clients.Contains(...))
The point notation applies to formulas which take value of type before point as one of arguments* (in this case List). These two records are equal:
Contains(Clients, Value) and Clients.Contains(Value)
However, the Not formula works with logic value, so you should first calculate logic value and only then pass it to Not. And yes, if there was NotContains formula as you suggest, this syntax would be possible: Clients.NotContains(...)
*P.S. With the same logic this is also valid: Clients.Contains(...).Not()