Ok, esse problema geral elevou sua cabeça feia duas vezes nos últimos 6 meses (procedimento armazenado diferente). Nossos usuários internos relatam um erro de tempo limite no aplicativo. Podemos reproduzir o problema na aplicação em um ambiente controlado. Então, seguimos as etapas normais de verificação de bloqueio usando sp_who2. Tudo parece bom sem bloqueio. Então, fazemos um rastreamento sql para ver exatamente como o procedimento está sendo executado. Copiamos isso para uma nova janela no SQL Management Studio e executamos o que o sql trace estava nos dizendo que o ADO.Net estava fazendo e terminou em milissegundos. O tempo limite de nossos aplicativos é de 30 segundos. Quando esse problema ocorreu alguns meses atrás, tínhamos o SQL Server 2005. Agora, atualizamos para o SQL Server 2008 R2. Qual é o próximo passo para diagnosticar um problema como este?

@ Martin: Obrigado pela resposta. Vou ler sua postagem em detalhes e informar o que descobri. Até lá, aqui está o sql no SP que você solicitou:

Select 
    @Exists=0, 
    @EarnRecId=0,
    @SuppStatusId = 0,
    @SLRecId = 0,
    @EarnRecDS = Null

Select
    @EarnRecId = er.EarningsId,
    @EarnRecDS = Convert(Varchar(26),er.Datestamp, 109),
    @SuppStatusId = s.SuppStatusId,
    @SLRecId = s.SLId
From
    Tracking tr
    Inner Join Supps s On s.SuppId = tr.SuppId
    Inner Join Earnings er On er.EarnRecId = s.SuppId
Where
    tr.ClaimId = @ClaimId
    and er.FiscalYr = @FiscalYr
    And er.EmplyrId In (@EmpId1,@EmpId2)

If @EarnRecId > 0
    Begin
        Set @Exists=1
    End