A similar thing was happeing to one of my sql server.

The reason was that the sproc was reading from a huge heap table (no primary key - clustered idnex) a lot of defragmentation. The delay was happening not entirely randomly but on the first 2-3 days of a new month. (the querries were manipulating data based on months)

The sollution was to create a Primary key (This took several hours and for an 100GB table the database grew 100Gb duting the process and afterwards it released those 100GB - internally not to the os , wich means that we needed to Shrink Datab se also afterwards).

In order to troubleshoot , use perfmon to setup some basic counters focusing mostly on I/O read write. We saw that on the days the sproc hang the I/O time was 100% for more than 10 times the average...