Jobs Running Stored Procedures Stall In Randon Places

Developers have complained that some of their jobs are taking too long to
run. I used Profiler to trace one really bad performer and could see that
the code was making one pass through its loop in about 7 seconds. I found
one select statement that was using the majority of the time, plugged it into
query analyzer and looked at the execution plan. It was using an index but
not very efficiently. I then ran it through index analysis and it
recommended a new index. This was cool! The new index helped.

But, the job continued to run very, very slowly - over a week before it died!
I ran another trace, and it was hanging for 10+ seconds in random locations.
Sometimes it would be on a database call, sometimes it would be on a simple
SET @variable = value statement. There was no pattern. According to the
sys admin, the server itself did not look taxed. It does not appear to be a
locking problem because of the random location of the stall. The application
and server are only lightly used at this point, so I would hate to see how
bad it could be if it was busy.

I am still fairly new to SQL, though I have years of DBA experience. I would
appreciate any ideas - especially the obvious things that I am probably not
considering. I have logged a call with Microsoft but they haven't gotten
back with an answer. I sent them a trace file and a perfmon file, neither
of which showed them anything.

Thanks!