Jag hade liknande problem med lagrade procedurer, och för mig visade det sig vara "parametersniffning". Googla på det och se om det löser ditt problem, för mig var det dramatiskt snabbare när jag fixade det.
I mitt fall fixade jag det genom att deklarera en lokal variabel för varje parametrar som skickades in, och sedan tilldelade den lokala variabeln till det parametervärdet, och resten av processen använde de lokala variablerna för bearbetning...av vilken anledning som helst, detta besegrade parametern sniffning.