Query lento con indices

Tengo un problema que me genera muchas dudas, tengo varios Store
Procedure que se ejecutan en un MsSQL con SP4 (el servidor tambien
tiene todos los SP) y cuando se procesan por primera vez tarda 24 seg
o 30 seg si lo vuelvo a ejecutar inmediatamente tarda 3 o 4 segundos,
pasados 7 o 10 min el tiempo de procesamiento vuelve a ser de 24 seg
o 30 seg.

Hasta ahora he realizado diferentes pruebas, en las cuales incluyo
detalle

1. Actualice todos los SP de la Maquina y de SQL Server

2. Verifique los indices de cada tabla (estan normalizadas), y tiene
los indices necesarios

3. Reralice pruebas con el Monitor de Rendimiento, el servidor no
presenta problemas de Procesamiento, Memoria o Disco (si vi bloqueos y
opte por otra prueba mas adelante), los usuarios que acceden no pasan
mas de 30 conexiones a diferentes tablas de la misma base de datos,
raramente sobrepasan las 10 conexiones concurrentes, es mas he probado
con consultas que solo puede ejecutar un cargo superior y no un
operador

4. Probe El plan de ejecucion estimado (tambien con SET SHOWPLAN_TEXT)
y en una de las tablas que no tenia un indice al agregarlo me degrada
el Query algunos segundos mas por lo que opte por sacar ese indice

5. Probe diferentes alternativas para acelerar el procesamiento aunque
me devuelva datos sucios a traves de SET TRANSACTION ISOLATION LEVEL
y tampo co lo mejora considerablemente siguiendo con el mismo tiempo
inicial

6 Como a traves del Monitor de Rendimiento vi algunos bloqueos
instale otro servidor con todos los SP y con un backup de la base de
datos sin meterlo en el dominio (sin ningun usuario accediendo y sin
ninguna otra aplicacion que pueda afectar, cabe destacar que tanto el
equipo original como el de prueba no son controladores de dominio por
si alguno lo penso...) para asegurarme que no hubiese otra aplicacion
pero me sigue dando los mismos tiempos iniciales

Un datos mas, No opero con Cursores que podrian estar planchando la
consulta

Obviamente que lo unico que me resta hacer es tratar de dividir el
Query que estoy tirando pero por las dudas lo consulto ALGUIEN LE
PASO ESTO...?, LO SOLUCIONO DE ALGUNA FORMA...?

Es decir porque la consulta inicial tarda mas si tiene todos los
indices necesarios y despues tarda lo que una base optimizada y normal

Desde ya muchas gracias