orientación búsqueda LIKE %texto% sobre 30.000 registros

Hola a todos ¿qué tal?

A ver, os cuento, que soy no tengo mucha experiencia en el manejo de miles
de registros. Escenario: SQL Server 7.0 al que ataco con Access 2000 desde
un ADP. Tengo una tabla con 30.000 registros y casi 50 campos que crecerá
del orden de unos 5.000 - 6.000 al año. Muchos de esos campos son VARCHAR
extensos e incluso TEXT.

Necesito buscar cadenas de texto en varios de esos campos, y lo hago con
LIKE '%cadena%' ... Esas consultas, medidas desde el Query Analizer, pueden
tardarme entre 25-30 segundos, y me dice en el plan de ejecución estimado
que es el table scan el que consume el 97% del proceso ¿qué se puede hacer
al respecto? ¿Lo estoy haciendo de la mejor manera posible? He leído algo de
los índices de texto ¿merece la pena en este caso? Por otro lado, NO veo el
servicio en los "Servicios de Compatibilidad" del SQL ¿cómo lo instalo?

Y para terminar... luego tengo que desarrollar un pequeño modulito de
búsqueda por intranet, a través de HTML y ASP, de ahí que trato de buscar la
mejor solución si es posible para aplicar después en ambos casos. Estoy un
poco desesperado y agradecería mucho vuestra ayuda

Gracias de antemano

Julius
Zaragoza