Hi Kerrie,
Either Mike B or Ralf should already have the data, as it's the same stuff we've been using for all our other issues. It's called MergedWest.mpk.
I don't have a sample app for you, but just using the QueryTask against the Streets layer of that data with a where clause like "NAME like '%SEARCH_STRING%'". I tried searching for a street called "E Northern Lights Blvd" starting letter by letter. So first it was '%N%', then it was '%No%' (we've since added a UNAME column with the names upper-cased, but you see the same behavior either way. Where it started timing out for me was about '%Norther%'. Any letters more than about 5 and it returned timeout exceptions. That layer has about 9,000,000 records in it, and we've also added indexes to the columns we are searching.
I'm also uploading the map pack with the UName column and indexes to our FTP site, you can get the details from Ralf or Mike B. It's called MergedWestUC.mpk. It's just over a gig, so it'll probably take a bit to complete. If you're still unable to reproduce then I'll put together a simple sample that replicates what we're doing for you.
Thanks,
James
If you still can't