that it is because of lack of memory. They have increased apache's maxclients setting
Look for another service provider.
If you don't have enough memory to service the current number of clients, then increasing the number of clients will make the problem worse.
First thing is to check that it's logging PHP errors properly (i.e. writing them to the webserver error_log). You can test this by simply accessing a (deliberately) badly written script, e.g.
Out-of-memory errors will be written to this error log - including details of which script was executing at the time and where it fell over.
You can also add code to record details of memory usage (e.g. with an auto-prepend script) rather than wait for it to fail. It would be a good idea to implement this via a registered shutdown function.
This should give you some priorities for re-factoring.
Meanwhile, as a seperate exercise, you should set a cron job to start logging the logging the number of httpd processes, and the amount of free memory e.g.
m=`free | grep '+'`
p=`ps aux | grep httpd | wc -l`
echo $t $m $p >> /var/log/webload
Then graph the results to get an idea of how many clients you can serve with a given amount of memory (NB since good I/O performance depends on caching, then depending on what I/O is going on on your system, you probably want to aim for around 50% of memory free).
This will also provide a mechanism for measuring how effective your refactoring is.
Increasing the max memory available to each PHP process is simply a matter of updating the php.ini file.
Do apply the usual process for PHP / webserver tuning - i.e. check caching, compression working optimally, log and analyse database queries.
NB sometimes you just need more hardware.