Parece um sniffing de parâmetros.

Aqui está uma boa explicação:Eu cheiro um parâmetro!

Basicamente, o sql server tem o plano de execução de consulta em cache para os parâmetros com os quais foi executado pela primeira vez, portanto, o plano não é ideal para os novos valores que você está passando. Quando você executa a consulta diretamente o plano é gerado naquele momento, por isso é rápido.

Você pode marcar o procedimento para recompilação manualmente usando sp_recompile ou use a opção With Recompile em sua definição para que seja compilado em cada execução.