Busquedas por Strings.

Mi consulta es la siguiente,

En mi base de datos tengo una tabla con alrededor de 6 000 000 de registros
de nombre de personas y empresas. Yo necesito realizar busquedas por nombre y
devolver a la aplicacion
las primeras 250 coincidendias, para eso utilizo el like '%' + StringABuscar
'%', y sobre el campo nombre tengo creado un indice. He realizado pruebas y
cuando realizo busquedas con coincidencias este me las devuelve en un tiempo
optimo, sin embargo cuando hago busqueda con palabras que no tienen
coincidencias sobre la tabla, la consulta agota el tiempo de expiracion del
sistema y el programa se cae. Alguien me puede dar una ayuda para resolver
este inconveniente.

. MI llave primaria es una identificacion de tipo numerica ya que necesito
trabajar con otras tablas relacionadas.

Gracias.

German.