Random error 500 – Premature end of script headers: php-script

My (WP 2.6.5) site at menz.org.nz is producing random “500 internal server error” messages, most noticable when trying to access wp-admin pages from the home page, but also when posting and editing. Often a refresh will return things to normal, but sometimes there are several 500 errors in a row.

This has been happening since at least WP 2.5, both to me and to other site users. About 98% of the time things are fine, so deactivating plugins is not particularly helpful.

The most common entry from my server error log is:

[Mon Dec 08 11:16:34 2008] [error] [client xxx.xx.xx.xxx] Premature end of script headers: php-script, referer: http://menz.org.nz/

There are seldom more than a dozen users on the site at any one time.

I have edited php.ini to increase: memory_limit = 32M
PHP Version 4.3.10
MySQL 4.1.18