Esta é a pegada do sniffing de parâmetros. Veja aqui outra discussão sobre isso; Desempenho ruim do plano de execução de procedimento armazenado do SQL - sniffing de parâmetros

Existem várias correções possíveis, incluindo adicionar WITH RECOMPILE ao seu procedimento armazenado, que funciona cerca de metade do tempo.

A correção recomendada para a maioria das situações (embora dependa da estrutura de sua consulta e sproc) é NÃO use seus parâmetros diretamente em suas consultas, mas armazene-os em variáveis ​​locais e use essas variáveis ​​em suas consultas.