Consulta lenta

Hola
Tengo un servidor en produción en SQL Server 2000, con el último service
pack. Mi problema es que cuando ejecuto un procedimiento con un valor
especifico este tarda mas de 1 minuto, mientras que con cualquier otra
consulta se ejecuta en menos de 2 seg. El procedimiento hace selects a
varias tablas y regresa varios record set.
Ya reindexamos y se sigue presentando. No importa la hora en que se ejcute
siempre tarda lo mismo. Ya revise los registros por si tenian algo raro y
no
encontre nada.
Al otro día la consulta se normaliza pero me presenta otro valor con el
problema. Tendrán alguna idea.