Ejecutar 1 Store Procedured tarda más que ejecutarlo en el SQL Analizer??

Hola a todos
Tengo un caso intrigante

Tengo un SP que realiza el cálculo de costes de 1 obra, 1 delegacion o de
toda la empresa según los parámetros que se pasen. Como podreis imaginar
es bastante complejo (1600 lineas), selecciona registros de muchas tablas
y es consultado continuamente por muchos usuario. Este procedimiento es
llamado por una aplicacion (VB6) que se conecta con ADODB.

El caso es que ultimamente tarda mucho en realizar el cálculo, no importa
lo que pidas (obra, delegacion o empresa). Los tiempos van de 50 seg. a
más de 1 minuto y medio. Habia pensado que quizas se me habian degradado
algunos índices, así que hice dbcc dbreindex( <tabla>,'') para todas las
tablas que usa el SP.

Vuelta a realizar pruebas y tampoco... que tarda lo mismo (o sea, mucho).

Me llevo el codigo del SP al SQL Analizer, sustituyo los parametros por
los valores y .. !!tarda 17-18 seg. en ejecutarse!!. Si en el mismo
Analizer escribo "EXECUTE <procedimiento> @param1, @param2." vuelve a
tardar más de 50 seg.

¿Cómo es posible esto? ¿Puede ser que el mismo procedimiento almacenado no
pueda ser ejecutado simultaneamente por 2 usuarios, que se cree un bloqueo
y hasta que no acabe el primero no sea ejecutado para el 2º?

Cualquier opinión al respecto sería de agradecer...