My host has tweaked the server as much as he can to ensure that it is performing optimally. We've upgraded the hardware twice, which made a small improvement each time, but not enough to warrant throwing even more hardware at it. We reboot it every few days as there is a very noticeable slowdown as time goes on. I also manually optimize the database every evening before going to bed. These two practices seem to help the most.

My host always points to the caching as a big problem. Part of the tweaks he did to the server were aimed at improving the cache system. I don't know enough about that stuff to tell you exactly what he did.

Thank you both for your replies.