Have you examined the headers of one of the emails sent to the Spam folder?
Message-ID is not a very good spam identifier.
Php uses the sendmail binary. You can supply an envelope sender globally, or within your php app as the 5th parameter to the mail() call.
Add -f sender@domain to your sendmail_path in php.ini. Eg:
sendmail_path = /usr/sbin/sendmail -t -i -f email@example.com
If you php app supplies the 5th parameter to mail(), you can override if necessary:
; Force the addition of the specified parameters to be passed as extra parameters
; to the sendmail binary. These parameters will always replace the value of
; the 5th parameter to mail(), even in safe mode.
Make sure the envelope sender is valid, or bounces won't be possible and undelivered mail disappears.