Gli SP sono precompilati, è possibile che venga utilizzato un piano di query "non valido" che non va bene per gli argomenti passati all'SP. Puoi aggiungere un OPTION (RECOMPILE) sulle query all'interno dell'SP per forzare SQL Server a rieseguire la query tramite Query Optimizer e trovare la query migliore per i parametri specificati.
Vedi qui o qui per alcuni esempi e informazioni di base...
