Подозирам надушване на параметри.
Опитайте да приложите анти-параметър снифинг код във вашата процедура. (Присвоете параметри на локални променливи, преди да ги използвате).
http://blogs .technet.com/b/mdegre/archive/2012/03/19/what-is-parameter-sniffing.aspx