Unlike Perl, PHP automatically sends the headers when a script first sends output to the browser, unless the script has previously sent the headers explicitly. I haven't used PHP in conjunction with SSI before, so I don't know how it handles that situation.
I'm just making a wild guess. This problem may have nothing to do with faulty headers.
Do you have zlib compression enabled? (another wild guess)
