"does not contain" in CAML?

The same restriction applies to BeginWith. I do not know any good solution sadly. What you could do: Do a Contains-Query, loop through each item and get the IDs, then do another big query for "ID NotEqual 1 or ID NotEqual 2 or ID NotEqual 3......" Since ID is indexed as far as I know, that should have a smaller impact on the database, but it still smells really bad.

For small list it does not matter, for larger lists i'd use the SQL Server Profiler to see what the impact is.

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