Interpreting the question
Firstly, I should state that I interpreted
"Since this is a FHE scheme that allows arbitrary computation, the cloud service builds a full-text search function on the ciphertext and starts querying E(M) to check for partial matches or even full equality of M"
to mean something equivalent to
"What if the cloud service uses the homomorphic properties of the ciphertexts to evaluate a search algorithm which outputs True if the searched substring is contained in the message, or alternatively outputs the matched substring, or returns any arbitrary information about the message. Why can't they abuse this feature to find the message?"
I mention this up front because there appears to be confusion about what exactly the question is asking. This answer will assume that the unspecified homomorphic encryption scheme fulfills its promise of data confidentiality, which for a fully homomorphic scheme, includes evaluating arbitrary circuits while revealing nothing of the plaintext value without evaluating the decryption circuit. Obviously, this does not extend to constants introduced during the evaluation that are created by the service provider via the public key (which they only know because they created the ciphertext).
With homomorphic encryption, the data is confidential to everyone but the key holder. Anyone can manipulate ciphertexts and evaluate functions on them, but they cannot decrypt the ciphertexts to obtain the result.
What part of FHE prevents the cloud service from doing this?
So the answer is that nothing prevents the cloud service provider from computing a search on the encrypted data - it may compute the search, but it cannot decrypt and view the result of the search. This is because the output of the circuit that is computed is also a ciphertext. The cloud service provider may compute any circuit it wants (assuming the scheme supports it), but the output will always be a bunch of random noise as far the cloud service provider is concerned.