Have only spent a little time this morning but turned up the following:

This post on a Drupal forum talks about a similar issue and possible solutions.

Also, this webserver tool shows that your host is using the end-of-life version of Apache [Apache/1.3.42] which *could* be causing problems.

Thanks so much for your time and your response. It is very much appreciated. I've contacted my hosting company to ask if they can switch me to a more recent version of Apache. I'll let you know what happens and if that solves this issue.

Hopefully it's that simple

And of course it wasn't that simple... This is the response I got, "The Apache version base that we are using on our servers is 1.3. Please note that we have modified and patched it with all the latest patches plus many custom solutions to make it operate as stable and securely and we do not have any recent plans on upgrading the server.

If your application needs a newer version of Apache, I would suggest that you consider upgrading your hosting plan to one of our Dedicated Solutions. There, the entire server environment will be dedicated to your account only, you will have full root privileges and will be able to modify and tweak the server to your particular needs."

At this point I'm not sure what to tell my client. Is there any other testing that I can do to more definitively point to whether this is an error caused by a corrupt or faulty script or an error caused by an old version of Apache.

Here's what I've done so far:
1. Checked my permissions on my files and folders. Everything seems to be in order.
2. Emptied my cache (more than once)
3. Ran Joomla debug - Got this "Notice: Trying to get property of non-object in /xxx/administrator/modules/mod_aamenu/helper.php on line 23 (and several others similar for different lines) ... I don't know if this has anything to do with my other issue. I think it may be due to something else. Interestingly, if I disable AAmenu, I get the same error message.
Profile Information
Application afterLoad: 0.001 seconds, 0.32 MB
Application afterInitialise: 0.126 seconds, 8.68 MB
Application afterRoute: 0.126 seconds, 8.68 MB
Application afterDispatch: 0.164 seconds, 10.07 MB
Application afterRender: 0.233 seconds, 10.89 MB
Memory Usage
11462580
4. Checked my cPanel error log and got messages such as File does not exist: /xxx/public_html/robots.txt and Premature end of script headers: xxx/public_html/1/index.php
5. Contacted my hosting company. They said they "found that the update script is looping upon execution which is causing the problem."
6. I performed a PHP memory test and found an error. "Fatal error: Allowed memory size of 100663296 bytes exhausted (tried to allocate 100663297 bytes) in /xxx/public_html/phpmemtest.php on line 15"
7. Since then my hosting company has been encouraging me to upgrade to a dedicated server.

I thought I would just recap everything here in case I'm missing some incredible clue. I'm guessing that the next best step would be to either encourage my client to rush their decision so that we can upgrade to the latest Joomla and hopefully that would fix the problem, if it is a problem with a buggy file. Or copy the whole site to another server to see if the issue repeats itself. Is there something else I should be doing here? What do you think the next best step forward is?

Thanks again for your assistance with this! Sorry this is a bit of an epically long message.

Oh my goodness... I can't believe I didn't do this first. Today I disabled and then enabled all of my plugins one by one. I found the culprit. It's a "Users Synchronisation" plugin. It is associated with something called Joobi. I'm guessing maybe the original designer must have been using it for something and then deleted it, but accidentally left one component in place. It doesn't seem to have anything to do with CB or any of the other plugins we are using.

Once that is disabled, everything seems to work properly again.

Another groovy mystery solved
/* note to self: never assume that someone's already disabled all 3rd party plugins */