mohaughn,

That is why I was saying I would not just run out making changes without first trying to understand what exactly is happening. Honestly, given the number of questions and complaints around exchange here recently I think the most prudent step would be some exchange administration training for the OP. Just my take though.
I couldn't agree more! Sure all the suggestions are fine, but I just have this gut feeling that we have a sort of "bigger picture" issue here?

I am sort of imagining a mature installation with an "if it ain't broke, don't fix it" mentality. Everything works fine until you start to hit capacity thresholds, then everything falls apart in most unpredictable ways.

There certainly doesn't seem to be any kind of preventative maintenance philosopy in place?

Also, we are told that this is not a dedicated server............. I wonder how much that clouds the issue?