>I have tables with more than four million rows and have used that syntax and haven't run into timeouts. Admittedly, I have a few procedures where I'll split it up into multiple queries, to limit the # of rows where the LIKE '%Value%' is used - but regardless, haven't run into timeout problems.

How big if your field length? Do you have a lot of words in those? Also, have you combined such search with several fields? Because, in our case, the user has about 17 fields on the form so combining such search would other fields would be catastrophic. Also, how long does your search result take? If this is under the Web, you are probably looking at an almost instant result.