Problemas con tiempos de expiracion de mi sistema

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.