That would make sense if it were bad parameter sniffing. All that takes is for the plan to be recompiled with atypical parameters passed in (e.g., the index gets rebuilt or stats get updated, and the next call of the procedure uses values for which most of the table would be returned, and a scan makes more sense than a seek).
Basically, any time the problem is caused by the procedure or query getting compiled with a new bad plan, you're going to see a sudden change in performance, not a gradual deterioration.
Also, on the FREEPROCCACHE front, while you definitely don't want to just run that willy-nilly against a production system, in a case like this where you have one known query that you're investigating, you can pass the sql handle or plan handle of that query to FREEPROCCACHE and remove just that plan.
That's a slight improvement over making everything recompile 🙂