He is using this one http://wordpress.org/extend/plugins/w3-total-cache/ and i suggest to use this one http://wordpress.org/extend/plugins/wp-super-cache/ Thats a DIFFERENT one! ^)
Originally you did not suggest he use a different one that he already had installed. And if you read down a little further, you would have known where the problem lies. And thus, my read before you post statement. Plus I think W3 Total Cache is favored over WP Super Cache at any rate. But, your suggestion is duly noted.
Check out WP Engine (search Google for it). Does all the hard work for you. I wouldn't host a Wordpress blog any other way.
Perhaps the problem comes from your hosting provider's servers. This is happend more on shared hosting services. I don't recommend to change your hosting company because your current service is one of the most reliable web hosts on the web. If your the speed is very important for you, you can try a dedicated server to get your blogs online.