GSquared (8/6/2012)
Restarting the SQL service is probably speeding things up by getting rid of poorly built execution plans from the cache. That might speed it up, for a while, but it's a really poor solution (as you already mentioned).
Absolutely right. Instead of restarting you could try dbcc freeproccache (also ugly). If that "solves" the issue you could try updating statistics (outdated statistics could cause bad plans).
When that doesn't help it may be caused by "parameter sniffing" (google on that to find more info). If you can't change the (vendor) software there is no real solution for this problem.