Ik had een soortgelijk probleem met opgeslagen procedures, en voor mij bleek het 'parameter sniffing' te zijn. Google dat en kijk of het je probleem oplost, voor mij was het een enorme versnelling toen ik het eenmaal had opgelost.
In mijn geval heb ik het opgelost door een lokale variabele te declareren voor elke parameter die werd doorgegeven, en vervolgens de lokale variabele aan die parameterwaarde toe te wijzen, en de rest van de proc gebruikte de lokale variabelen voor verwerking ... om welke reden dan ook, dit versloeg het snuiven van parameters.