Was getting irregular "500 Internal Server Error" pages on a new Drupal 6 install, running on shared hosting.
After some research it appears that the hosting company is running php5 as CGI which does not follow the PHP directives set in Drupal's .htaccess file:
# PHP 4, Apache 1.
<IfModule mod_php4.c>
php_value magic_quotes_gpc 0
php_value register_globals 0
php_value session.auto_start 0
php_value mbstring.http_input pass
php_value mbstring.http_output pass
php_value mbstring.encoding_translation 0
</IfModule>
# PHP 4, Apache 2.
<IfModule sapi_apache2.c>
php_value magic_quotes_gpc 0
php_value register_globals 0
php_value session.auto_start 0
php_value mbstring.http_input pass
php_value mbstring.http_output pass
php_value mbstring.encoding_translation 0
</IfModule>
# PHP 5, Apache 1 and 2.
<IfModule mod_php5.c>
php_value magic_quotes_gpc 0
php_value register_globals 0
php_value session.auto_start 0
php_value mbstring.http_input pass
php_value mbstring.http_output pass
php_value mbstring.encoding_translation 0
</IfModule>
This post suggests commenting out these PHP specific settings, and adding the following to your php.ini (if you have access to it - some hosting companies don't allow this, although there are workarounds):
magic_quotes_gpc 0 register_globals 0 session.auto_start 0 mbstring.http_input pass mbstring.http_output pass mbstring.encoding_translation 0
This seems to work - I'll update in the comments if I run into this issue again.