Hi,
For the symptoms described, can be a bad cardinality issue or parameter sniffing issue.
Basically, you ended with a wrong execution plan that causes the unexpected delays in your jobs.
When you restart the instance, all the execution plans are wiped out and when the jobs run again, it creates a new one.

If there is a bad cardinallity issue, by updating the statistics will solve it.
If there is a parameter sniffing issue, removing the plan from memory, can mitigate the issue, but more research will be required.

Hope this helps.

.