It not depends on parameters, when System reaches the "degrade point" the store appears slow for different params ...
It simply use a bad execution plan, avoid using a index created for this type of query ...
The only two things unlock the situation are :
- Rebuilding Store Procedure
- Update Statistic of table in which store works
Are there situations where SQL Server doesn't update statistics regolary???
The is a some relation between the load of the systems (when application was under load by several users) and the reaching of the "degrade point".
System in this state seems ignore the index (specific for this query) presence .... and so use a different execution plan.
Recreate the procedure with "WITH RECOMPILE", and see how it goes for a week. You will incur a small performance penalty on each run, as the query compiles, but that may be more acceptable than waiting 70 seconds at random.