There seems to be a lack of readily accessible information out there about rolling your own search on a very Large table (VLT).  I spent a ridiculous amount of time trying to performance tune a query that searches a table of 16 million rows.   That shouldn't be a problem right?  After all, Microsoft SQL Server is designed for doing just that.  So I made a full-text catalog on a couple of columns.  Slow.  Anywhere from 11 seconds to a couple minutes.  I made an indexed view over the data.  Same thing.  I created all different types of indexes.  Same thing.

So, many moons later, we finally were able to get a fast search.  It turns out that the data file for that DB was 16 GB; that's right: the text data in the other columns of my VLT that weren't being used by the full-text catalog, were still negatively affecting performance.  So we made a new DB with a new table containing only the columns used in the Full-Text catalog, which brought the file size down to 1.6 GB or so.  Now we have a much more reasonable search, coming in from 1 to 4 seconds.  We also implemented table partitioning, which, unfortunately, is only available with the Enterprise Edition of SQL Server.  Many queries now respond in less than 1 second.

If the actual execution plan or SQL itself had said "Dude, the reason this is taking so long is because of the other columns in your table that you're not even using for your search", then I think we would've been on the right track a long time ago.