Jeg havde lignende problem med lagrede procedurer, og for mig viste det sig at være 'parameter sniffing'. Google det og se, om det løser dit problem, for mig var det dramatisk fremskyndelse, da jeg fik rettet det.
I mit tilfælde løste jeg det ved at erklære en lokal variabel for hver parameter, der blev sendt ind, og derefter tildelt den lokale variabel til den parameterværdi, og resten af processen brugte de lokale variabler til behandling... uanset årsagen, dette besejrede parameteren sniffing.