SQL Server - procedimiento almacenado time out

Al ejecutar un procedimiento almacenado desde aplicación C# en situación normal tarda unos 6 segundos. este mismo procedimiento cuando se trata de otro usuario se queda en maquina con la CPU al 25% y se eterniza vieniendo a tardar minutos o retornando Time Out. No ocurre siempre para el mismo usuario, pues también le puede pasar al primero. También puede que no le pase a ninguno usuario y se tire así varios días.
Hemos realizado pruebas, reorganización de tablas indices, aumentado la TEMPBD para que no se extienda, y el problema persiste. ¿Que puede ser?.

Mucgas gracias.

En tu analizador de consultas, setea

SET STATISTICS IO ON

Y luego ejecutas tu store procedure.

Revisas las lecturas y le das tunning a tu procedure.