Roughly around the same time every morning the same error message shows up mutliple times per second for about 1 minute.

Oct 20 07:08:34 sm-www3 kernel: Out of Memory: Killed process 10572 (mysqld).

There is only 4 sites on this box and during the time period this happens there traffic is just starting to ramp up for the day. This never happens during their peak usage time.

The box is a 1.3GHz Celeron with 1GB of Ram. The box has MySQL ver. 4.0.20.

I've run through the optimization How-To on EV1's forums but still no luck.

Check for any scheduled tasks on the box. Maybe there is a stats update, backup process, or system update that takes up alot of memory at that time.

Excellent suggestion. There were some exim_tidydb tasks kicking off at 6AM. I moved those back to 2 and 3AM.

Adjusting the cron jobs didn't fix it. The problem seems to move around between 6AM and 8AM. Any other suggestions?

Get the server to do a ps -aux every 5 minutes at around that time and email them to you, or write them to a file with a date and timestamp.

Check your logs, and then reference the ps output.