Support

Most likely you were lacking the correct RewriteBase from Joomla!'s standard .htaccess file (it is commented out by default and you have to modify it manually). The .htaccess Maker feature in Admin Tools Professional automatically generates the correct RewriteBase tag so I think that it shouldn't cause a problem.

Alternatively, you can also set the $live_site parameter in your configuration.php file, as detailed in our friend Anything Digital's web-site. Even though they mostly talk about it in context of sh404SEF, the $live_site parameter may affect any site, no matter which SEF extension it uses, or even those sites which do not use SEF at all. In my view, if you have such intermittent problems you should add that parameter. If that solves the problem, your client was half-right: it's a slight incompatibility between your host and Joomla!.

Finally, I strongly suggest turning on Admin Tools Professional's "redirect non-www to www" feature, as it can also resolve such issues and help your SEO by reducing the duplicate content recorded by Google and other search engines.