Quick note: It would be very helpful when posting problems to specify your EXACT configuration. You say you're using IIS4, which indicates MS Windows NT 4. However, it's often helpful to say something like
"I am running the Brasilian Portuguese version of MS Windows NT 4 SP5, IIS4, and the PHP v.4.0.4 CGI module."
Anyway, that aside, I believe your issue may have nothing to do with the header() function and everything to do with a well-known session bug in the Windows PHP engine. For details, see my initial bug report
http://www.php.net/bugs.php?id=5493
and followup bug report when the same damn bug resurfaced
http://www.php.net/bugs.php?id=8989
I have not yet tested 4.0.5, but in a nutshell, the last working Windows version of PHP that did sessions properly was the 4.0.3pl1 CGI module. I never verified the ISAPI module on that either, but when time permits, I will.
The problem is basically that session IDs do not transfer from page to page. But it only occurs every so many pages. It's weird. If you create the page1.PHP-page4.php files, then load page1.php and follow the links, you will see that new session files keep being generated (and since they are new sessions, the variables registered are basically null). Please note that I am assuming you are just using session files, as opposed to overwriting the functions so that you log session ids into a database, etc.
Which reminds me. Make sure you have configured PHP.INI in the \WINNT directory so that it points to a valid directory for session files. For example, I created a directory "sessions" in the E:\InetPub directory. I then set the appropriate entry in PHP.INI:
...
session.save_path = "E:\InetPub\sessions" ;
...
This is VERY important. By default, this parameter is NOT set properly, as "/tmp" is not valid in Windows.
Assuming you have your box configured properly, the only thing to watch is what version of PHP you are using. Again, I have not tested all the versions yet, but the last known version to work properly was the 4.0.3pl1 CGI module. If you configure your system with this version (NOT using the ISAPI module mind you), it should work. It does for me, both under the English versions of Windows NT4 SP5/IIS4 and Windows 2000/IIS5 (with either SP1 or SP2).
Hope that helps at least a little. I've been teaching a friend of mine ASP (VBScript basically) so he can try to land a job doing basic web development, and I'll tell ya, I do not like it. I think PHP is FAR easier to use. So hopefully you can get those people converted to PHP. As for reasons, where to begin? :-)
Anyway, good luck with Conectiva. I wish you success.
Até logo.