So what is the best way to get the
items that do not contain a string?
Try using a calculated column to reflect the value you are looking by creating the opposite value.
For example, say the column is called IsCritical. Then, add the column as a "YES/NO" and the formula as
=ISNUMBER(FIND("Critical"), [Title])
Then in your CAML query
<Query>
<Where>
<Eq>
<FieldRef Name='IsCritical'/>
<Value Type='Boolean'>0</Value>
</Eq>
</Where>
</Query>
A 0 in this query kinda reflects "Is Not Critical". However I am not sure what the performance may be as opposed to having a native CAML "Not Containts" which unfortunately does not exist.
See Also CAML Query Schema at MSDN