• It may be the case of parameter sniffing, alter procedure with WITH RECOMPILE and try.