Insisto con que el Full-Text Indexes es la solución. El problema es que jamás he tenido necesidad de usarlos y no los conozco. Pero esto es lo primero que lees en la ayuda:
Cita:
Iniciado por BOL A Microsoft® SQL Server™ 2000 full-text index provides efficient support for sophisticated word searches in character string data. The full-text index stores information about significant words and their location within a given column. This information is used to quickly complete full-text queries that search for rows with particular words or combinations of words.
Documentate al respecto para que desarrolles tu solución en este sentido.