I don't see how any query can avoid a table scan given a condition like "all company names that contain the word THE".
I have used this technique to meet some complex requirements for a flexible search proc. I structured the code a little differently by placing the constant first (before the case). From my reading of SARGs I think (don't know) that would help performance some. Also, I always include a default value for the Case.
e.g. where 1 = Case .......
else 1
end