one of the things to keep in mind, is that many PHP based programs modify the mail headers - so it may look like it is coming from domain.com but the actualy machine name is localhost.localdomain or just localhost - and the true mailer is the apache service or php service (many times its the apache).

So your PHP script sets it to be From: Your Name <name@domainnamehere.com> but the system appends it to be from apache@localhost or something like that.

So often the spammers setup machines to bulk email and would spoof the headers so with many ISPs when the PHP script modifies the headers it is picked up as spam, like wise with email client filters.

Just another avenue to check on.