Desgaste de los procedimientos almacenados

Estimados: Tengo un procedimiento almacenado el cual contiene una consulta
que involucra la union 6 tablas. Actualmente este procedimiento tarda un
minuto en entregar los resultados, lo cual es bastante condiderando la
simpleza de la consulta y la poca cantidad de registros.

Tome la consulta que estaba contenida el el procedimiento almacenado y la
ejecute el Query Analizer y solo tardo 1 segundoraro????

Procedi a crear un nuevo procedimiento almacenado con la misma consulta del
procedimiento anterior y tambien tardo 1 segundo en ejecutarse.

El resumen tengo 2 procedimientos almacenados ambos con la misma consulta.
Uno tarda 1 minuto y el otro un segundo.

¿A que se puede deber?
¿Sera un cache?
¿Habra que recompilar el procedimiento?

Espero me puedan ayudar.

Saludos,
Christian M.