Вы абсолютно уверены, что запрос, выполняемый в sp, всегда один и тот же? Например, возможно ли, что когда он замедляется, запрос имеет другой порядок сортировки? Возможно, 9 раз из 10, запрос возвращается быстро, и в 10 раз медленнее, поскольку получаемые данные сортируются по некоторому столбцу, который не проиндексирован?
В этих ситуациях я бы попытался настроить трассировку SQL (используя sql profiler) и позволить ей какое-то время работать. Как только ситуация произойдет, дайте ей пройти, а затем проанализируйте трассировку. Вне всякого сомнения, подтвердите, что выполняемый запрос такой же, как и другие выполнения того же sp