Further research shows others having no problem with PHP 5.6.
Changing affected PHP version to 7.0.X.

I think this is the same as my issue. There seems to be an extra character before the additional headers. For example:

mail("to@email.com", "Subject", "Message", "From: from@email.com");

To: <to@email.com>
X-PHP-Originating-Script: 0:test.php
 From: from@email.com
From: <from@email.com>

An additional From header is added and this causes it to be blocked when sent to gmail addresses. On the other hand, if I put a dummy header before it:

mail("to@email.com", "Subject", "Message", "X-PHP-Fix: x\r\nFrom: from@email.com");

To: <to@email.com>
X-PHP-Originating-Script: 0:test.php
 X-PHP-Fix: x
From: <from@email.com>

This is sent successfully to gmail addresses. My guess is that this is the lone CR or LF that is causing his emails to fail. I have one server running 7.0.10 that is affected and one running 5.3.13 that is not affected, which matches his experience.

I don't think this is PHP doing this. At least not directly. Which MTA are you using? The first thing to understand here is that by default PHP just invokes an external MTA to send an email with the mail() function on non-Windows machines. The program that is run is defined by your sendmail_path ini setting. This also means we can override it to examine what exactly PHP is sending to the MTA program.

Here is a test. Create this trivial PHP program:

#!/usr/local/bin/php
<?php
file_put_contents("/tmp/test.log", file_get_contents("php://stdin"), FILE_APPEND);

I called mine /home/rasmus/sm and I made it executable (chmod +x ./sm)

Then I tried your example script of:

<?php
mail("to@email.com", "Subject", "Message", "From: from@email.com");

I ran it like this:

php -d sendmail_path="/home/rasmus/sm" m

The output I see in /tmp/test.log is:

To: to@email.com
Subject: Subject
From: from@email.com

Message

What I think is happening here, at least for mattcoz at yahoo dot com is that the user invoking the MTA is not conifgured to be a trusted user and as such is not allowed to override the From address. The MTA inserts the space in front of it and adds its own From line.

For sherwoodsports at gmail dot com, what is your mail() line that is producing that error? As you can see from my minimal test it doesn't appear that PHP is inserting an extra cr-lf in the headers. Again, it is likely some sort of interaction with your MTA.

I'm running Windows, so the MTA is not an issue. Also, I have no problem overriding the from address. I think I found where the problem might really be though. My server had the mail.add_x_header preference set to On for some reason. When I switch it to Off I no longer get the space before the rest of my headers. I'll open a new bug report for this specific issue and leave it Off on my server because I really don't need it.

We have test cases for multiple headers by additional_headers parameter.
http://lxr.php.net/xref/PHP-7.0/ext/standard/tests/mail/mail_basic6.phpt

> mail("to@email.com", "Subject", "Message", "X-PHP-Fix: x\r\nFrom: from@email.com");

This shouldn't produce following headers.

> To: <to@email.com>
> X-PHP-Originating-Script: 0:test.php
>  From: from@email.com
> From: <from@email.com>

I suppose this is your MTA issue.

If you think this is a bug in PHP, try to add bug case to 
http://lxr.php.net/xref/PHP-7.0/ext/standard/tests/mail/mail_basic6.phpt

You can run the test in PHP source build like

TESTS=ext/standard/tests/mail/mail_basic6.phpt make test

Attach modified mail_basic6.phpt file and reopen this bug.

Hold up...  the comments posted are not related to the original report.  Please do not identify this bug with those comments then mark this bug as "not a bug" due to your analysis of the issue identified in the comments.

I opened a new bug for my issue: https://bugs.php.net/bug.php?id=73507

Like I mentioned, you should provide "bug case", not creating new bug report.

PHP is not the only program modify mail header, so you should provide case that PHP produces malformed mail headers.

BTW

To: <to@email.com>
X-PHP-Originating-Script: 0:test.php
 From: from@email.com
From: <from@email.com>  <--- PHP never adds this 

by 

mail("to@email.com", "Subject", "Message", "From: from@email.com");


Current mail() accepts multiline header, i.e. it allows too long line folding by  "\r\n ", "\r\n\t", but it never split lines automatically.

It trims unneeded chars at the first and end, detects malformed newlines, but it never add modified headers by parsing addtional_headers.

If you have problem, please try to reproduce by modifying the phpt file that I've mentioned.

OK. Back to original report.

Could you modify the test script and attach the modified test script (the phpt) so that the problem can be seen as plain text output?

OS should not be "All". Are you using Windows or UNIX like OS? (Windows and UNIX uses different code to send mails) Please specify what OS you are using.

Again, your comment is unrelated to the original bug report.  Please re-open this bug.  I am unable to compare output between 5.3 and 7.0.  This is what needs to be done to determine if this original report is a bug or not.

I will modify and will send the output as soon as I can but am unable to for a day or two.

This is on Windows server 2008.

I reopened this bug for the time being.
It seems this problem is due to MTA/UMA newline conversion which is not a bug of PHP.

Recent MTA/UMA do _not_ convert LF to CR/LF and this could results in errors like you have. It seems you are experiencing this issue and if this is the case, you should fix your code. i.e. Use CR/LF for new lines as defined in RFC.

Thank you for re-opening.  

A manipulated MTA/UMA likely would not explain why the older version of PHP works, but the newer version does not.  

Also, all CRLF's used in the code are using PHP_EOL and are not using manual ('\n\r') characters to end lines.  No single \r or \n characters are used, therefore are not subject to the non-conversion issue you suggest.  This also supports the fact that the older PHP versions prior to 7 works without issues, but 7 does have issues.

Are you sure that you are using the same MTA (mail server) and UMA (sendmail binary) for old and new PHPs? If not, MTA/UMA behavior change is the cause most likely.

If you are using the same MTA/UMA, please modify following test script and reproduce issue.

https://github.com/php/php-src/blob/master/ext/standard/tests/mail/mail_basic.phpt

Unfortunately, I'm in a Windows Server 2008 R2 environment.  After reading it, that script indicates right away that it won't run on Windows.

I use the IIS web server to swap PHP versions that IIS is using for any given web site.  The SMTP server is Microsoft CDO (basically Microsoft Exchange Libraries) and it has never changed (this library is no longer updated via Microsoft) between various server web languages (ASP, PHP 5.3.24) and has only experienced issues with PHP 7 and above.  All that said, it would be difficult to say a library that has never changed is suddenly sensitive to PHP 7 (I still have PHP 5 installed and it still doesn't fail).

Do you have a script that will run on Windows?  Is there a command that fails on Windows that I can modify in that script such that it will run successfully?

No feedback was provided. The bug is being suspended because
we assume that you are no longer experiencing the problem.
If this is not the case and you are able to provide the
information that was requested earlier, please do so and
change the status of the bug back to "Re-Opened". Thank you.

You can configure SMTP to dump to a pickup directory:
https://technet.microsoft.com/en-us/library/cc772058(v=ws.10).aspx

Alter the path to $outFile in the test script appropriately, comment out the SKIPIF code, and you should be able to run the test code.

No feedback was provided. The bug is being suspended because
we assume that you are no longer experiencing the problem.
If this is not the case and you are able to provide the
information that was requested earlier, please do so and
change the status of the bug back to "Re-Opened". Thank you.