Trace Analysis
I began from making an analysis of the whole trace and sorting it by the duration of stored procedures:

On the chart diagram, I found some activity in regular intervals:


List of transactions does not indicate anything wrong:

However, what is interesting is in the distribution chart for the individual procedures:

It is clearly visible, that the execution time of that procedure is irregular; sometimes it is more then 10 times longer then usual

The same is applicable to the second procedure.
It might be an indication of locks. Unfortunately, the given trace does not contain a column CPU. CPU is useful as an indication of possible lock waiting. Lines/statements with high Duration value but without a lot of Reads, Writes and CPU are good indicators of that problem. If statement did not wait for IO and CPU – then the only thing which could delay an execution is a lock.
I found some deadlocks in a trace:

Looks like DBA is aware of that problem. Deadlocks usually are a visible part of an iceberg of locks, so I am almost confident there are many locks.
3 deadlocks events are always associated with connections 103 and 54:
SPID 103 exec <proc
name removed>
SPID 54 .<proc name removed>
You can not only correlate these 3 events to the peaks of execution visible on the distribution chart for <proc name> and <proc name>, but also you can see they can be correlated together. If you select them both:

They are so correlated so one graph is
almost completely covered by another one:

We can also see other events, did not manifested as deadlocks, but caused a slowdown (for example,
between
So my diagnosis is: suffering from locks and deadlocks, mostly between <proc name> and <proc name>, but not limited to these 2 procedures.
Further steps:
Don’t hesitate to contact us if you have any questions.
Dmitry Tsuranoff
SQL Product Support
Phone: (206) 851 1541
Fax: (206) 260 3826
Web: www.sqlsolutions.com