I had similar issues with a server I was renting from 1&1: the never ending "there-is-a-problem-no-there-isn't" two-step shuffle. Well actually it ended when I sent a formal complaing and they agreed to terminate my contract early - no questions asked.
Now with another provider which costs more but has been 100% reliable in the last 5-6 months I have been with them (great support and sale team too).
The root might have been filling up with logs not rotating or tmp files being created + not purged <- wild guess really, I'm not an expert.