procmail and php email issues

[omoutop]

Hello all and thanks in advance for any suggestions/tips.
Also, sorry if this is the wrong forum, but its the only relevant one i can think of.

synthesis:
Apache 1.3.37
PHP Version 4.4.2
MySQL 4.1.19

Some time ago, 1-2 months, we (the company i work for) decided to monitor some email conversations between our clients and our site visitors.
For that purpose, we used procmail (suggested here in webmasterworld).
During this period, all monitored conversations were being saved in databse, filtered automatically from anything we do not wish to show yet. We were also cloaking the original email address with something like [e-mail] and [e-mail].
When our customers and our visitors came to a deal, and when the visitors decided to pay a sum in advance for a service, we released the conversation from monitorin status, send all contact info from both parties to each other - case closed.

During the last week (around 10 days actually), we were having problems with email acounts from yahoo.com and hotmail.com.

While the original email is being delivered to these addresses, their reply never reaches the recipient.

Scanning in the headers of the emails, we discovered some issues with our email server (lack of proper spf), which we fixed (asked support of the server for this).

Yet the problem is not solved.
In the headers of the emails, we see this:
Authentication-Results: mta240.mail.re4.yahoo.com from=mysite.com; domainkeys=neutral (no sig).

We werent able to determine what that is.
And we hope that fixing this will fix our problem as well.

If we send a normal email to yahoo or hotmail, all works well. The problem of email not being recieved when it is a reply email, only appears in the procmail emails.

So, what can we do/ask for this?
And, are there any other suggestions on improving our email server? We have consult with some free tools on the web, and the results seems ok.

If it is of any importance/use, these are the headers of the original email (the first one - before any replies):

$init = md5(microtime());
$header = "Return-Path: [e-mail]\n";
$header .= "Reply-To: [e-mail]\n";
$header .= "From: some department <[e-mail]>\n";
$header .= "MIME-Version: 1.0\n";
$header .= "Content-Type: text/html; charset=iso-8859-7;\n";
$header .= "X-Mailer: PHP 4.x\n";
$header .= "Message-ID: <".$init."@mysite.com>\n";