A lower bound on the insecurity of CipherCloud?
That paper refers to the numerical ordering, while what would be relevant for searchable encryption without changes to the providers is the substring ordering. $\:$ (Thus, their bound does not apply.)

What do you mean by "existing queries in a database"?

If your assumption holds, then
{
Encryption must be deterministic (given the key), since different encryptions of the

same message (with the same key) must be substrings of each other (and thus equal).

There must be a noticable $\big($though not necessarily $\theta\hspace{.01 in}(1)\big)$ chance of breaking authenticity via a

single ciphertext only (by submitting a random substring of it). $\:$ The scheme must be malleable by

almost the same amount, again with just a single ciphertext only and for basically the same reason.
}

"without changes to the providers" is a rather stiff assumption. $\:$ For example, one could easily shut

down active attacks by splitting the ciphertexts into two columns and having the cloud just search the

left column, while the right column has message authentication codes which are only relevant to the user.