Take a look at the manual page for [man]header/man... specifically, look at using the optional second argument.
EDIT: Oops... the default is to replace, apparently (could've sworn it was the other way around :o).
I haven't tried this with an ErrorDocument handler, but I would assume that PHP can override the default header that Apache sets. I'll try to duplicate that in my test environment, but first... what version of PHP and Apache are you using? Is PHP installed as an Apache module or a CGI binary?
Also, have you turned display_errors On and set error_reporting to E_ALL?
EDIT2: Also, have you tried using the 3rd parameter for [man]header/man? Although it shouldn't be necessary, try doing something like:
header('HTTP/1.1 200 OK', true, 200);