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).

I suggest that your best bet for the server is to download a free copy of Confio Ignite, set it up to monitor that server, and take a look at what it tells you are the worst queries on it. It will summarize the data in a very easy-to-read graph, and make it very clear what's slowing things down.

That's assuming you'll be able to actually modify anything in terms of database objects, queries, and so on. Can you, or is all of that embedded in the code that you can't modify?

You can get Ignite free from here: http://www.ignitefree.com/

Disclosure: I'm not an employee, blah blah blah, of Confio, and have no vested interest in you getting it. I'm just a DBA who finds it really, really useful for seeing what's slowing down a server. Especially a server that I'm not familiar with yet. Quest Foglight/Spotlight/Performance Monitor will do more, give you more data, and cost more, than Ignite. Go with that if you want to dig into the data to that extent. I suggest Ignite only because it's free, and easier for a non-DBA to use.