Intermittent and Random Page Not Found Errors on website running Drupal 5.10

Hello,

I am looking for help on a problem on my website (www.unbreakablegaming.com) that has been going on for two months. The main problem is, I am getting an intermittent Page not Found error randomly by the user all over the site. The page not found error will always show up looking themed, and not a browser generated connection error. Here is a sample of what I usually see:

Sample 1: http://farm4.static.flickr.com/3198/2932077348_41c666f32a_b.jpg
Sample 2: http://farm4.static.flickr.com/3025/2931222037_61a1716909_b.jpg

The error appears randomly for all users and it can hit from any part of the website - going to the frontpage, clicking on a forum link, clicking on a forum post, reading a private message, opening the Admin page, etc. There is only one place where I can guarantee duplication of the page not found error every time, and that is doing a search on the website. Doing a search will always give me that error, where as in just browsing the site, it happens randomly. When the error happens, the page usually takes a long time to load.

How bad is the error? My current user population is around 120 users with an average of 20 long term visits in 24 hours by those users. It is a small, but dedicated population. Those visits at the highest point of the error generated 13,767 page not found errors over 14 days or about 1000 page not found errors in 24 hours. Through the steps I will detail below, I now have the errors down to about 118 in 24 period...but it is still happening and randomly. These drops in errors can also be misleading, because the users are not staying on the site as long as they used to because of the errors...so the site is getting less use.

What triggered the error? I am not sure, but it did not happen instantly. It progressed to a point where the site became unusable. I did upgrade the site from Drupal 5.2 to 5.8 in late July, but the site worked great for several days before this showed up; but it was fine for many months before this change running on 5.2 and 5.1. I have had problems with CPU/Server load, which makes the error much worse. It is running on a shared server, so if the load is high the problem becomes much more apparent. I have worked with the hosting company, and load issues on the server have been much better.

A little bit about my current configuration:

Drupal 5.10
MySql 4.1.22
PHP 4.4.4
JQuery 1.2.6
Webserver details: Apache/1.3.37 (Unix) mod_fastcgi/2.4.2 mod_gzip/1.3.26.1a mod_auth_pass through/1.8 mod_log_bytes/1.2 mod_bwlimited/1.4 FrontPage/5.0.2.2635.SR1.2 mod_ssl/2.8.28 OpenSSL/0.9.7a PHP-CGI/0.1b
Hosting Company: Site5
Current theme for users: RoopleThemes BealeStreet

Current modules installed:
Access Control: Content Access, Forum Access
Core Optional Mods: Blog, Blog API, Book, Comment, Forum, Help,Menu, Poll, Profile, Search, Statistics, Taxonomy, Throttle, Tracker
Development (installed to help troubleshoot this issue): Devel, Devel Node Access, Generator, Macro
Mail: Privatemsg
Node Profile: Usernode
Optional: Remember Me
Other: Advanced Forum, BBCode, FlatForums, Members, Pathauto, Quote, ThemeSettings API, TinyMCE, Token
SWF Tools: jquert.flash.js, SWF Tools, Wijering Flash
Spam Control: ASCII art Captcha, Captcha, Image Captcha, Phrase Captcha, ReCaptcha, Word List Captcha
User Interface: Jquery Update
User Goodies: Signatures for Forums, User Stats
Views: Action View, View, Views Argument API, Views RSS, Views Theme Wizard, Views UI, Views Union
Voting: Voting API
Voting API: Advanced Polls.

Steps I have taken:
-Moving to other simpler themes...Garland, etc..Theme changes seem to offer no improvement to this error. I have not eliminated this, but the error happens whether I am using Garland or a more complex theme.
-Confirming that all modules are the latest version - I have made sure that all existing installed modules are the most recent version available for Drupal 5.x. With that said, it could be a module that I have installed that does not like Durpal 5.8 or 5.10.
-Upgraded the site from Drupal 5.8 to 5.10 and ran update.Phip.
-Removing Modules: I have slimmed down the number of features the site has running by removing modules down to the ones the users make the most use of. I could cut back more, but I will start impacting the most used features of the site. Cutting back modules has seemed to improve the problem as the number of times the error happens in a day has been greatly reduced (from a 1000 a day to 100 a day) since doing this. With that said, I have not found the magic problem module that has eliminated this error.
-Installed Devel: After much reading, I installed this module to see if it could help me pinpoint the problem. Unfortunately, I just don't have enough development skill to interpret all of the data that does come back.
-Ran update.php a few times to make sure it is not a menu rebuild issue. I read somewhere that this could be the cause, and this is how it could be fixed.
-Review of error_log: There is not an error line created in the drupal error_log on the server when the page not found happens. I do have a series of errors dating back to Aug 24, which is related to a loss of connection to the database server when the hosting company had an outage. There is nothing in this log that I can tie directly to this error.

Theory: I do have a theory, but it is more anecdotal than evidence based. I believe the more links a page has on it when it comes up, such as the Admin page or a forum view page listing all current posts with links, the more likely it is to happen. With the page load times taking longer when this error occurs and it seems to happen on pages that have more links.....can it be related to database or webserver timing out and I am just getting a wrong error code?

Anyway, It is a lot of information I put up, but I have exhausted all forum searches, drupal documentation, and testing that I could find over the last 2 months. So, it is time to ask for help. Any ideas are appreciated.

Thanks,

Rich