> The interesting thing is that those tests do not contain any of these columns (on which we have set the search type) in the where clause.
That would be unexpected. You'll want to compare the query plans from the searchable and non-searchable versions of one of these queries. From your description they should be the same. If they are different the "set showplan debug" full debug log can help identify what has changed.
We have a bunch of queries executing in the test, we are trying to figure out the exact query causing the problem, once we have that, will post the query plan.