I'm unable to reproduce this with PHP 4.0.6RC1.
Please try it: http://www.php.net/~andi/php-4.0.6RC1.tar.gz

And also, replace your php.ini with the php.ini-dist that
comes with the package. Then change the appropriate directives.

--Jani

No feedback, considered fixed.

It appears this problem as I described earlier does exists in PHP 4.0.6.

Mea Culpa. 

The problem was caused by a PHP script designed to strip slashes from $HTTP_POST_VARS when magic_quotes_gpc are enabled but unwanted (ie, in situations where one does not have the authority to turn magic_quotes_gpc off). 

It simply applied stripslashes() to each element of $HTTP_POST_VARS but this is not enough as a POST variable may be an array.

This was indeed the case in my checkbox example.

I have since written this function to stripslashes correctly (it works "in place", caveat emptor):

function & stripallslashes ( &$variable ) {
 // strip slashes recursively (works around magic_quotes_gpc)
    if ( gettype($variable) == "array" ) {
        reset($variable);
        while ( list($key,$value) = each($variable) )
            $variable[$key] = stripallslashes($value);
        return $variable;
    } elseif ( gettype($variable) == "string" )
          return stripslashes( $variable );
    else return $variable;
}

Applied to HTTP_POST_VARS thus:

   stripslashes($HTTP_POST_VARS);

resolves the problems I was having.