Heve you tried using a view to create the result set to search? I assume you are trying to so something like list1 union list2 union list3 and then do a lookup on a column from the resulting set. By using a view you can capture the initial exec plan and see how to optimize it, then your sp should just do a lookup in the result set's column. If you are using SQL server enterprise version it will even allow you to index the view, plus if you are using a parameter to query the view in the sp it will prefilter your result set.

-R!