if it went a way after altering the proc, and then came back after a few hours, i'd start suspecting that stale statistics were affecting performance of the existing plans;
if you look at the tables used by the proc, are any of them MillionBillionRow tables and have a large amount of insert/updates/deletes to them?
can you update statstics for the tables used by teh proc and see if there is an immediate improvement?
Lowell