Sounds like either "bad" parameter sniffing. You can check the parameter values for the slow runs to normal runs by using ExecutionLog3.Paramters column and see what values are causing the skew.

Updating statistics on the table(s) involved can potentially solve the problem as well. It really depends on the shape of the data in the table(s). If you have data skew, for example in phone book, Smith vs. Xavier, where the best plan for SMith is a scan and the best plan for Xavier is a seek, and you get a seek for Smith because Xavier was the value sniffed at compile time, you'll have issues. Then you can use something like OPTION RECOMPILE or OPTIMIZE FOR in your query to help the query perform consistently.