Lentitud en el primer llamado de un sql o de un procedimiento

La primera consulta sobre una tabla es muy lenta sin importar si lo hago
por un sp o con un sql directamente sobre la tabla, estube consultanto y
tiene que ver con el sp_recommpile pero ya lo ejecute para todos los
procedimientos de la base de datos y lo que hace es marcar para recompliar
lo que aumenta mi problema, lo que necesitaria es que no recompile que
trabaje con la compilacion que tiene, hay que tener en cuenta que la cosa es
mas critica en una tabla que tengo con mas de un millon de registros pero en
general pasa con todas, cuando la base de datos es grandecita "Casi un giga"
con msde 2000.
Lo mas raro es que este servidor no se apaga diario y el problema es con el
primer registro diario.
Que debo hacer ?????.