Check the sys.dm_exec_requests DMV. What are the long running queries waiting on?
Have you rebuilt indexes recently?
Does recompiling the procedure make any difference? (EXEC sp_recompile 'StoredProcName')
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)SQL In The Wild
: Discussions on DB performance with occasional diversions into recoverability
We walk in the dark places no others will enter
We stand on the bridge and no one may pass