Please try using this CVS snapshot:

  http://snaps.php.net/php4-STABLE-latest.tar.gz
 
For Windows:
 
  http://snaps.php.net/win32/php4-win32-STABLE-latest.zip

I've tried the code & looked over the source and there is nothing that would 'strip' newlines as you suggest. If they are still being stripped in the new code I would say it is the doing of your sendmail binary.

It wasn't the sendmail binary, because after encountering the problem I've moved to call sendmail directly via popen(), and e-mail sending works this way properly (ofcourse I'm passing the same multiline $subject 
variable to sendmail through fputs).

I've found the part of the code I believe to cause the problem in ext/standard/mail.c (in the source of the latest, 4.3.1 release, though I encountered the bug itself in 4.2.3 first):

PHP_FUNCTION(mail)
{
/* ...cut... */ 
if (subject_len > 0) {
 for (; subject_len; subject_len--) {
  if (!isspace((unsigned char) subject[subject_len - 1])) {
   break;
  }
  subject[subject_len - 1] = '\0';
 }
 for(i = 0; subject[i]; i++) {
  if (iscntrl((unsigned char) subject[i])) {
   subject[i] = ' ';
  }
 }
}
/* ...cut... */

The second 'for' cycle must be responsible for replacing all the new line characters to spaces. I think it was used because the developers wanted to avoid the extra leading/trailing linefeeds in the Subject: line (that also leads to send incorrectly formatted (and displayed) e-mails).

If you agree, I'd suggest replacing this part of code to another one which is trimming only the leading/trailing control characters - or even a more sophisticated one that would format the subject line to conform to RFC 822, 
part 3.1.1 "Long header fields", part 3.4.8 "Folding long header fields".

[In fact, I'd suggest doing these modifications also to the recipient address (the 'To:' field) for the same reason.]

This bug has been fixed in CVS.

In case this was a PHP problem, snapshots of the sources are packaged
every three hours; this change will be in the next snapshot. You can
grab the snapshot at http://snaps.php.net/.
 
In case this was a documentation problem, the fix will show up soon at
http://www.php.net/manual/.

In case this was a PHP.net website problem, the change will show
up on the PHP.net site and on the mirror sites in short time.
 
Thank you for the report, and for helping us make PHP better.

Keep in mind that your code will still not work as is, RFC 822 specifies that the "separator" must be CRLF followed by atleast one \t or a space.
This means you should use \r\n\t and not \n\t.

The subject line is in Japanese text and is extremely long, so that it takes several minutes to open.  It can not be deleted and also can not be opened.