Problema de desempenho do procedimento armazenado do SQL Server 2005

Algumas opções:

O que faz o criador de perfil ou SET STATISTICS xx ON dizer? Existe simplesmente falta de recursos, digamos CPU

O mecanismo decide que as estatísticas estão desatualizadas. As tabelas estão mudando em 10% de mudança na contagem de linhas (regra geral). Testar:

SELECT
    name AS stats_name, 
    STATS_DATE(object_id, stats_id) AS statistics_update_date
FROM
    sys.stats 
WHERE
    object_id IN (OBJECT_ID('relevanttable1'), OBJECT_ID('relevanttable2'))

O que mais está acontecendo no servidor? exemplo:Reconstrução de índice:não bloqueando, apenas com uso intensivo de recursos.

Normalmente, eu sugiro o sniffing de parâmetros, mas você diz que os parâmetros são os mesmos para todas as chamadas. Eu também esperaria que isso acontecesse com mais frequência.